A graph on vertices 1 to n started as a tree, and then one extra edge was added. Return an edge that can be removed so the graph becomes a tree again. If several answers exist, return the one that appears last in the input.
Before you code
The extra edge created exactly one cycle. Which edge of that cycle is the last one to appear in the input, and what happens at the moment it is processed?
Hints
- Process the edges in input order, with one union-find group per vertex.
- Union the endpoints of each edge. While unions succeed, the edges so far form a forest.
- The first edge whose endpoints already share a root closes the cycle, and it is the last of the cycle's edges in the input. Return it.
Production & complexity notes
When solving Redundant connection on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Disjoint sets to reinforce the underlying pattern.
What it practices
Cycle detection with union-find, from Disjoint sets.