Direct flights
Airports are numbered from 1 to n; some pairs are connected by direct flights in both directions. Find the largest group of airports in which every two are connected by a direct flight.
The third test is the real air network: 3468 airports and all pairs with flights in both directions; the fourth is the 200 best-connected of them. The other tests are dense graphs where there are many such groups, intertwined.
Input
The first line holds n and m (1 ≤ n ≤ 3500, 0 ≤ m ≤ 5 · 10⁴). Then m lines, the pairs of connected airports, each once. In tests where n is greater than 200 the graph is sparse.
Output
The first line is the size of the group k, the second k airport numbers. If there are several groups of the largest size, print any.
Examples
Example 1
6 9 1 2 1 3 2 3 3 4 3 5 3 6 4 5 4 6 5 6
4 3 4 5 6
Example 2
4 2 1 2 3 4
2 3 4
Limits
- Time · Python
- 12500 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is the maximum clique problem, and there is no fast algorithm for it. What remains is a search: add vertices connected to all already taken. How can you avoid opening branches where the incumbent cannot be beaten?
2Hint 2
“Taken plus all candidates” is a weak bound: in a dense graph there are a hundred candidates and a clique of twenty. Colour the candidates so that vertices of the same colour are not neighbours. How many vertices of a clique can have the same colour?
3The idea
Branch and bound with a colouring bound: a clique is no larger than the number of colours, since its vertices are pairwise neighbours and so all of different colours. The colouring is greedy, anew at each node; candidates are tried from the highest colour to the lowest, and the colour number of the current vertex is a bound for everything that remains.
4Walkthrough
The initial order is by decreasing degree. At a node, colour the candidates, write them out by colour and take them off from the end: if “taken + colour” is no greater than the incumbent, the branch is finished; otherwise take the vertex, keep among the remaining ones only its neighbours, and go down. The recursion depth is at most the size of the clique, under forty.
4+Solution
5Complexity
Exponential in the worst case, but on the tests the search tree ranges from 242 nodes on the air network to 27 thousand on the hardest dense graph. A colouring costs O(k²) comparisons per node with k candidates.
6Common mistakes
- The candidate-count bound. This is
wrong.py. On the air network it makes it in time, as the graph is sparse, but on the dense graphs from the fifth test on the search grows to millions of nodes. - Colouring once. If you colour only at the root, the bound inside branches gets coarse: a subgraph needs fewer colours than the whole graph.
- A strict comparison. Prune when “taken + colour” is no greater than the incumbent; with a strict sign the answer is right, but the tree is noticeably larger.
- Greed. “Take the vertex with the most neighbours among the remaining candidates” gives a large clique but not the largest: 35 airports instead of 38 on the air network, 19 instead of 22 on the seventh test. As a first incumbent it is useful.