A tree with n nodes had one extra edge added. Return the edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.
DSA Animator › DSA Revision › Graph › Redundant Connection
Remember: an edge whose ends already share a root closes a cycle. Union find answers connectivity questions almost in constant time. The video solves Redundant Connection (LeetCode 684, Medium) with the Union Find pattern from the Graph topic, and you can replay every step in the interactive Redundant Connection animation.
A tree with n nodes had one extra edge added. Return the edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.
For the edges 1 2, 2 3, 3 4, 1 4 and 1 5, the answer is 1 4. It closes the cycle 1, 2, 3, 4.
You could remove each edge in turn and check whether the rest is a tree. That repeats a full graph search for every edge.
Process the edges in order with union find. At the start, every node is its own group. For each edge, find the root of both ends. If the roots differ, merge the two groups. If the roots are already equal, the two nodes were already connected, so this edge forms the cycle, and it is the answer.
Edge 1 2 merges nodes 1 and 2. Edge 2 3 adds node 3 to the same group. Edge 3 4 adds node 4. Edge 1 4: nodes 1 and 4 already have the same root. So 1 4 is the redundant edge, and we return it. The edge 1 5 is never needed for the answer.
In code, create a parent array where each node points to itself. The find function follows parents to the root, compressing the path on the way. For each edge, if find of both ends is equal, return that edge. Otherwise set the parent of one root to the other, which is almost O of n overall.
Remember: an edge whose ends already share a root closes a cycle. Union find answers connectivity questions almost in constant time.