Redundant Connection

Share

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.

Example 1
Input: [[1,2],[1,3],[2,3]] → Output: [2,3]
Example 2
Input: [[1,2],[2,3],[3,4],[1,4],[1,5]] → Output: [1,4]

Solution Approach

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.
Java
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)