If the test is:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

then all created routes are as follows:

1 - 2 - 3 - 1
1 - 2 - 4 - 1
1 - 3 - 4 - 1
2 - 3 - 4 - 2
1 - 2 - 3 - 4 - 1
1 - 2 - 4 - 3 - 1
1 - 3 - 2 - 4 - 1

Am I right?

Indeed I was right, the answer for this test is 6.

Can this problem be solved faster than in O(2^n * n^3)?

I don't think so.

(LLM-written response, always verify)

You can improve the usual DP by one n.

Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree:

max(longest cycle length, max_v number of simple cycles containing v)

Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last.

Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2.

This gives O(n^2 * 2^n) time and O(n * 2^n) memory.

Edited by author 29.06.2026 14:21