O(n * α(n)) O(n)
Intuition
Add edges one by one with union-find. The graph is a tree plus one extra edge, so the first (and only) edge whose endpoints already share a root is the redundant one. Scanning in order returns the last such edge automatically.
Explanation
Why the first union-failure is the answer
The input is a tree with exactly one extra edge, so processing edges left to right, every edge merges two components until the one edge that connects two already-connected nodes — that edge closes the cycle and is redundant. Because there is only one extra edge, this first union-failure is also the last valid answer in input order.
Walk-through
parent = list(range(n+1))
for a, b in edges:
if find(a) == find(b): return [a, b]
union(a, b)
edges = [[1,2],[1,3],[2,3]]:
- (1,2): union.
- (1,3): union → {1,2,3}.
- (2,3): find(2) == find(3) → cycle → return [2,3].
Complexity
- Time: O(n·α(n)).
- Space: O(n).
Implementation
class Solution {
private int[] parent;
public int[] findRedundantConnection(int[][] edges) {
parent = new int[edges.length + 1];
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (int[] e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return e; // this edge closes a cycle
parent[ra] = rb;
}
return new int[]{};
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}