Why it works
- While the ends of an edge have different roots, the edge only joins two groups and adds no cycle. An edge whose ends already share a root has a path beside it, so together they make a cycle.
- A cycle is complete only when the last of its edges in the list arrives, so the first edge found this way is the cycle edge that comes last: the very one to return.
- Edges after it are not on the cycle, since the graph has only one, so the run stops there.
Complexity
Time O(n · h): two finds per edge, as deep as the trees, which is up to n here and almost a constant with re-hanging on the root and the smaller tree under the bigger. Memory O(n) for parent.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗