A tree with n nodes originally had n - 1 edges. One extra edge was added, creating exactly one cycle. Given the edges, return the edge that can be removed to restore a valid tree. If more than one edge would work, return the one that appears last in the input.
Example
Input edges = [[1,2],[1,3],[2,3]]
Output [2,3]
Key Pointers
Union-Find applies directly: process edges in order, and the first edge whose endpoints are already in the same component is the redundant one.
"Return the one that appears last" falls out naturally from processing left to right and returning the first edge that fails to union.
No separate cycle-detection DFS is needed — Union-Find's return value (whether the union actually merged two different components) is exactly the cycle check.
Step-by-Step Analysis
Initialize a Union-Find parent array, one entry per node.
Process each edge (a, b) in input order: find the roots of a and b.
If the roots are already equal, a and b were already connected — this edge is redundant, so return it immediately.
Otherwise union the two components and continue to the next edge.
Complexity
Time: O(n · α(n)) — Space: O(n)
Code
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
n = len(edges)
parent = list(range(n + 1))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return [a, b]
parent[root_a] = root_b
return []
Code Explanation
How the solution above works, piece by piece.
The input is a tree plus one extra edge. Process edges in order with Union-Find.
For edge (a, b), find both roots.
Same root: a and b are already connected by earlier edges, so this edge closes a cycle. It's the redundant one; return it.
Different roots: merge the groups and continue.
Because edges are processed in input order, the edge returned is the last one that creates the cycle, as the problem asks. Nearly O(n).
Visual Walkthrough
Running it on edges = [[1, 2], [1, 3], [2, 3]]:
Shown: parent[1..3]. Edges 1–2 and 1–3 merge everything into one group, so when 2–3 arrives both ends already share root 3: that edge is redundant.