Redundant Connection
Medium· Union-Find
Problem
A tree with n nodes (labelled 1 to n) had one extra edge added, so the given edge list now contains exactly one cycle. Return an edge you can remove to get back a tree; if there are several, return the one that appears last in the input.
Examples
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Edges 1-2, 2-3, 3-4 already connect 1 and 4, so 1-4 closes the cycle.
Constraints
- • n == edges.length
- • 3 <= n <= 1000
- • The graph is connected and has no repeated edges
Hints & approach
Hint 1
Add edges one by one and keep track of which nodes are already connected.
Hint 2
An edge whose endpoints are already in the same component creates a cycle.
Approachtry the hints first
Process edges in order with union-find. For each edge [u, v], find the roots of u and v; if they match, this edge closes a cycle and is the answer. Otherwise union them. Since the first edge that closes the single cycle is also the last cycle edge in input order, returning it satisfies the tie-break rule.
Time O(n * α(n)) · Space O(n)