The problem
A tree with n nodes had exactly one extra edge added. Given the edge list, return the edge that can be removed so the graph becomes a tree again (if multiple answers, return the last one in input order).
Stuck? Reveal hints one at a time
How to approach it
- 1Initialize Union-Find with each node as its own parent.
- 2Process edges in input order. For each edge (u, v), find the roots of u and v.
- 3If the roots are equal, u and v are already connected — adding this edge would close a cycle. That edge is the answer.
- 4Otherwise union the two roots and continue.
Key insight
Processing edges in order and returning the FIRST cycle-closing edge automatically satisfies "return the last valid answer" — every earlier edge was needed.
The solution
Watch out for
- Nodes are 1-indexed — size the parent array n+1.
- Without path compression the find can degrade to O(n) per call on adversarial chains.