Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

685. Redundant Connection II - Leetcode Solution

Problem Description

You are given a directed graph that started as a rooted tree with n nodes labeled from 1 to n with exactly n-1 edges. Then, one extra directed edge was added, possibly causing two types of issues:

  • A node has two parents (i.e., two edges point to the same node).
  • There is a cycle in the graph.

You are given a list edges where each element is a pair [u, v] indicating a directed edge from u to v. Your task is to find and return the redundant directed edge that should be removed to restore the tree structure. If there are multiple answers, return the one that occurs last in the input list.

Constraints:
  • There is exactly one edge to remove to make the graph a rooted tree.
  • All node labels are unique and between 1 and n.
  • Do not reuse or alter elements; simply return the redundant edge.

Thought Process

At first glance, this problem seems similar to the classic "Redundant Connection" problem, but the added complexity is that the graph is directed and a node may have two parents. A brute-force approach would be to remove each edge one by one and check if the resulting graph is a rooted tree, but this is inefficient for large inputs.

To optimize, we need to consider the two possible issues separately:

  • If a node has two parents, one of the incoming edges must be removed.
  • If there is a cycle, we need to remove an edge that breaks the cycle.
The trick is to identify which edge (if any) causes a node to have two parents, and then determine whether removing it or another edge (in the case of a cycle) will restore the tree.

This leads to a two-step process:
  1. Detect if any node has two parents, and record the two edges involved.
  2. Use Union-Find (Disjoint Set Union) to detect cycles, ignoring one or the other of the two-parent edges as needed.
This approach allows us to efficiently find the redundant edge without brute-force checking every possibility.

Solution Approach

Let's break down the solution into clear steps:

  1. Detect a node with two parents:
    • Iterate over all edges and track the parent of each node.
    • If a node is found with two parents, record both edges: candidate1 (first incoming edge) and candidate2 (second incoming edge).
  2. Union-Find to detect cycles:
    • Initialize a Union-Find structure for all nodes.
    • Iterate over edges again:
      • If there is a two-parent situation, skip candidate2 for now.
      • For each edge, perform a union operation:
        • If the union fails (nodes already connected), a cycle is detected.
  3. Decide which edge to remove:
    • If no node has two parents, remove the edge causing the cycle (as in the classic redundant connection problem).
    • If a node has two parents:
      • If skipping candidate2 leads to no cycle, remove candidate2.
      • If skipping candidate2 still results in a cycle, remove candidate1.

Why Union-Find? Union-Find is ideal for cycle detection in graphs, as it allows us to efficiently check whether two nodes are already connected (i.e., part of the same set).

Data Structures Used:
  • A parent array (or map) to track the parent of each node.
  • A Union-Find (Disjoint Set Union) structure for cycle detection.

Example Walkthrough

Let's walk through an example:

Input: edges = [[1,2], [1,3], [2,3]]
Step 1: Find node with two parents

  • Edge [1,2]: parent of 2 is 1
  • Edge [1,3]: parent of 3 is 1
  • Edge [2,3]: 3 already has a parent (1), so now it also has 2 as parent
  • So, node 3 has two parents: [1,3] and [2,3]
Step 2: Union-Find, skipping [2,3]
  • Union 1-2: OK
  • Union 1-3: OK
  • Skip [2,3]
Step 3: Is there a cycle?
  • No cycle detected when skipping [2,3]
Conclusion: Remove [2,3]
Output: [2,3]

Time and Space Complexity

Brute-force Approach:

  • For each edge, remove it and check if the resulting graph is a rooted tree.
  • Checking for a rooted tree takes O(n), and there are O(n) edges to check, so total is O(n^2).
Optimized Approach (Union-Find):
  • Finding a node with two parents: O(n)
  • Union-Find operations for all edges: nearly O(n) (with path compression and union by rank, amortized O(α(n)) per operation)
  • Total time: O(n)
  • Space: O(n) for parent arrays and Union-Find structure
Why? Each edge and node is processed only a constant number of times, and Union-Find is very efficient for this kind of connectivity check.

Summary

The key insight is to recognize the two possible problems: a node with two parents and a cycle. By carefully tracking parent assignments and using Union-Find to detect cycles, we can efficiently determine which edge to remove. This approach is both elegant and efficient, avoiding brute-force checks and leveraging classic graph algorithms to restore the tree structure with minimal work.

Code Implementation

class Solution:
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        parent = {}
        cand1 = cand2 = None

        # Step 1: Check whether there is a node with two parents
        for u, v in edges:
            if v in parent:
                cand1 = [parent[v], v]
                cand2 = [u, v]
                break
            parent[v] = u

        # Union-Find
        def find(u, uf):
            while uf[u] != u:
                uf[u] = uf[uf[u]]
                u = uf[u]
            return u

        def union(u, v, uf):
            pu, pv = find(u, uf), find(v, uf)
            if pu == pv:
                return False
            uf[pv] = pu
            return True

        # Case 1: No two parents
        if not cand1:
            uf = [i for i in range(n + 1)]
            for u, v in edges:
                if not union(u, v, uf):
                    return [u, v]
        else:
            # Try skipping cand2
            uf = [i for i in range(n + 1)]
            for u, v in edges:
                if [u, v] == cand2:
                    continue
                if not union(u, v, uf):
                    return cand1
            return cand2
      
class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1, 0);
        vector<int> cand1, cand2;

        // Step 1: Check whether there is a node with two parents
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] == 0) {
                parent[v] = u;
            } else {
                cand1 = {parent[v], v};
                cand2 = {u, v};
                break;
            }
        }

        // Union-Find
        vector<int> uf(n + 1);
        for (int i = 0; i <= n; ++i) uf[i] = i;

        function<int(int)> find = [&](int u) {
            if (uf[u] != u) uf[u] = find(uf[u]);
            return uf[u];
        };

        auto unionSet = [&](int u, int v) {
            int pu = find(u), pv = find(v);
            if (pu == pv) return false;
            uf[pv] = pu;
            return true;
        };

        if (cand1.empty()) {
            for (auto& edge : edges) {
                if (!unionSet(edge[0], edge[1])) return edge;
            }
        } else {
            for (auto& edge : edges) {
                if (edge == cand2) continue;
                if (!unionSet(edge[0], edge[1])) return cand1;
            }
            return cand2;
        }
        return {};
    }
};
      
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        int[] cand1 = null, cand2 = null;

        // Step 1: Check whether there is a node with two parents
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] == 0) {
                parent[v] = u;
            } else {
                cand1 = new int[] {parent[v], v};
                cand2 = new int[] {u, v};
                break;
            }
        }

        // Union-Find
        int[] uf = new int[n + 1];
        for (int i = 0; i <= n; ++i) uf[i] = i;

        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int u) {
                if (uf[u] != u) uf[u] = applyAsInt(uf[u]);
                return uf[u];
            }
        };

        java.util.function.BiPredicate<Integer, Integer> union = (u, v) -> {
            int pu = find.applyAsInt(u), pv = find.applyAsInt(v);
            if (pu == pv) return false;
            uf[pv] = pu;
            return true;
        };

        if (cand1 == null) {
            for (int[] edge : edges) {
                if (!union.test(edge[0], edge[1])) return edge;
            }
        } else {
            for (int[] edge : edges) {
                if (edge[0] == cand2[0] && edge[1] == cand2[1]) continue;
                if (!union.test(edge[0], edge[1])) return cand1;
            }
            return cand2;
        }
        return new int[0];
    }
}
      
var findRedundantDirectedConnection = function(edges) {
    const n = edges.length;
    let parent = {};
    let cand1 = null, cand2 = null;

    // Step 1: Check whether there is a node with two parents
    for (let [u, v] of edges) {
        if (parent[v] === undefined) {
            parent[v] = u;
        } else {
            cand1 = [parent[v], v];
            cand2 = [u, v];
            break;
        }
    }

    // Union-Find
    let uf = Array(n + 1).fill(0).map((_, i) => i);

    function find(u) {
        while (uf[u] !== u) {
            uf[u] = uf[uf[u]];
            u = uf[u];
        }
        return u;
    }

    function union(u, v) {
        let pu = find(u), pv = find(v);
        if (pu === pv) return false;
        uf[pv] = pu;
        return true;
    }

    if (!cand1) {
        for (let [u, v] of edges) {
            if (!union(u, v)) return [u, v];
        }
    } else {
        uf = Array(n + 1).fill(0).map((_, i) => i);
        for (let [u, v] of edges) {
            if (u === cand2[0] && v === cand2[1]) continue;
            if (!union(u, v)) return cand1;
        }
        return cand2;
    }
};