Peel away the dead ends
Strip off places with only one road, again and again, and what remains is the loop. About 14 minutes.
Dead ends can't be on a loop
Suppose a network of villages has exactly one loop, plus some roads that branch off it and end. A village with only one road is a dead end, and a dead end can't be part of a loop, because a loop needs two roads at every village.
So cut away every dead end. After that, a village that used to sit one step in may now have only one road left, so it is a dead end too. Keep going. The branches get eaten from their tips inward, and the loop is left untouched.
degree = [len(adj[i]) for i in range(n)]
- dead_ends
- 5, 6
Places 5 and 6 each have only one road, so they are dead ends.
What is left
Use a line of villages to remove, just as in the earlier topological order. Take one out, mark it removed, and lower the road count of each neighbour that is still there. If a neighbour's count drops to 1, it has become a dead end and joins the line.
When the line is empty, every village not marked removed lies on the loop. Collect them, in increasing order if the question asks. This only works for a network that is connected and has exactly one loop.
removed = [False] * n removed[node] = True
A village has three roads. Two are removed as dead ends hang off it. What is its road count now?
- A1, so it becomes a dead end too
- B3, nothing changes
- C2, so it stays
Show the answer
1, so it becomes a dead end too. Its road count dropped from 3 to 1, so it is now removed next.
Which places are on the loop
There are n places, numbered 0 to n − 1, joined by n two-way roads, so that every place can reach every other and there is exactly one loop. edges[i] = [a, b] means a road between place a and place b. No two roads join the same pair of places, and no road starts and ends at the same place. Return the places on the loop, in increasing order.
n = 6, edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [1, 5]] → [0, 1, 2]
3 ≤ n ≤ 100,000