#684
Redundant Connection
Medium Union-Find
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A tree with n nodes had one extra edge added. Return an edge that can be removed to leave a tree (if several, the one that appears last in the input).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: which extra edge turned the tree into a graph with a cycle?
Why this works: add edges with Union-Find; the first edge whose ends are already connected closes the cycle.
Example: [[1,2],[1,3],[2,3]]
1-2 join, 1-3 join, 2-3 already connected → [2,3]✦Hints open one at a time
Add edges one by one with Union-Find.
The first edge whose two ends are already connected creates the cycle.
↗Approach
DSU with path compression and union by size. For each edge, if find(u) == find(v), return it; otherwise union them.
</>Solution (Java)
class Solution {
private int[] parent, size;
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
parent = new int[n + 1];
size = new int[n + 1];
for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
for (int[] e : edges) {
if (!union(e[0], e[1])) return e; // already connected: this edge closes a cycle
}
return new int[0];
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path compression (halving)
x = parent[x];
}
return x;
}
private boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
}!Common mistake
Skipping path compression — still correct, but finds can become slow on long chains.
Complexity
- Time: O(n · α(n)) ≈ O(n).
- Space: O(n).
Topic: Graphs
🎬 Episodes 74–85: video coming soon