DSA problem
Redundant Connection
In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. Return an edge that can be removed so that the resulting graph is a tree of n nodes.
Because the original tree has exactly n - 1 edges and one extra edge is added, the resulting graph has n edges and exactly one simple cycle. Any edge on that cycle is a valid candidate for removal, but the problem asks for the edge that occurs last in the input — so we should iterate the edges in input order and return the first one that closes a cycle.
The Union Find (DSU) data structure is purpose-built for detecting cycles incrementally. We process each edge [u, v] in order: if find(u) == find(v) then u and v are already in the same component, so adding this edge would create a cycle — return it immediately. Otherwise we union(u, v) and continue.
The advantage of this approach over DFS is that we never have to rebuild the adjacency list each time we try to remove an edge. With path compression and union by rank, the entire algorithm runs in O(n * alpha(n)) ~ O(n) amortised time and uses O(n) extra space.
Examples
edges = [[1,2],[1,3],[2,3]][2,3]edges = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,4]edges = [[1,2],[2,3],[1,3]][1,3]Constraints
- n == edges.length
- 3 <= n <= 1000
- edges[i].length == 2
- 1 <= ai < bi <= edges.length
- ai != bi
- There are no repeated edges, and the graph is connected.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.