Course4all
Join us on telegram
Home/dsa/Union Find/Redundant Connection II

Redundant Connection II

Master this topic with zero to advance depth.

Redundant Connection II

In this problem, a rooted tree is modified by adding exactly one extra edge. The extra edge is directed from parent to child. The resulting graph can have two issues:

  1. A node has two parents.
  2. There is a directed cycle.

Strategy

  1. Check if any node has two parents.
  2. If yes, test if removing the second edge fixes everything. If not, the first edge was the problem.
  3. If no node has two parents, simply find the edge that completes a cycle using Union-Find (like Redundant Connection I).
Hard

Examples

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Approach 1

Level I: DFS (Recursive Search)

Intuition

This problem involves finding an edge whose removal leaves a rooted tree. We can try removing each edge one by one and check if the resulting graph is a valid rooted tree (all nodes reachable from a single root, no cycles) using DFS.

⏱ O(N^2) by testing removal of each of the N edges.💾 O(N).
java
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        for (int i = n - 1; i >= 0; i--) {
            if (isValid(n, edges, i)) return edges[i];
        }
        return null;
    }
    private boolean isValid(int n, int[][] edges, int skip) {
        List<Integer>[] adj = new ArrayList[n+1]; for(int i=1; i<=n; i++) adj[i]=new ArrayList<>();
        int[] in = new int[n+1];
        for(int i=0; i<n; i++) if(i != skip) { adj[edges[i][0]].add(edges[i][1]); in[edges[i][1]]++; }
        int root = -1; for(int i=1; i<=n; i++) if(in[i]==0) { if(root != -1) return false; root = i; }
        if(root == -1) return false;
        Set<Integer> visited = new HashSet<>(); dfs(adj, visited, root);
        return visited.size() == n;
    }
    private void dfs(List<Integer>[] adj, Set<Integer> vis, int u) {
        vis.add(u); for(int v : adj[u]) if(!vis.contains(v)) dfs(adj, vis, v);
    }
}
Approach 2

Level III: Union-Find + Case Analysis

Intuition

Handle two cases: Case 1 is a node having two parents (two edges pointing to it). Case 2 is a simple cycle. Use DSU to detect which edge completes a cycle after potentially 'skipping' one of the double-parent edges.

⏱ O(N \cdot \alpha(N)).💾 O(N).
java
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1], cand1 = null, cand2 = null;
        for (int[] e : edges) {
            if (parent[e[1]] != 0) {
                cand1 = new int[]{parent[e[1]], e[1]};
                cand2 = new int[]{e[0], e[1]}; e[1] = 0; // Temporarily invalidate cand2
            } else parent[e[1]] = e[0];
        }
        int[] root = new int[n + 1]; for (int i = 1; i <= n; i++) root[i] = i;
        for (int[] e : edges) {
            if (e[1] == 0) continue;
            int r1 = find(root, e[0]), r2 = find(root, e[1]);
            if (r1 == r2) return cand1 == null ? e : cand1;
            root[r1] = r2;
        }
        return cand2;
    }
    private int find(int[] p, int i) { return p[i] == i ? i : (p[i] = find(p, p[i])); }
}
← Previous QuestionBricks Falling When Hit
Next Question →Critical Connections in a Network