Given a tree with one extra edge, find the redundant edge that when removed leaves a tree. Return the edge that appears last in the input.
Input: [[1,2],[1,3],[2,3]] → Output: [2,3]Input: [[1,2],[2,3],[3,4],[1,4],[1,5]] → Output: [1,4]
Process edges one by one with Union-Find. The first edge that connects two already-connected nodes is the redundant edge.
- Initialize parent[i]=i for i from 1 to n.
- For each edge (u,v): if find(u)==find(v): return [u,v] (redundant).
- Else union u and v.
class Solution {
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 pu = find(e[0]), pv = find(e[1]);
if (pu == pv) return e;
parent[pu] = pv;
}
return new int[]{};
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
}
- Time Complexity: O(N * alpha(N))
- Space Complexity: O(N)