LeetCode 685 - Redundant Connection II

The problem asks us to identify a redundant edge in a directed graph that originated as a rooted tree. A rooted tree has a single root with all other nodes having exactly one parent.

leetcodeharddepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 685

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks us to identify a redundant edge in a directed graph that originated as a rooted tree. A rooted tree has a single root with all other nodes having exactly one parent. The graph given is initially a tree with n nodes labeled 1 to n, with exactly one extra directed edge added. This extra edge may create either a cycle, a node with two parents, or both.

The input edges is a list of pairs [ui, vi], where ui is the parent of vi. We need to return one edge to remove such that the resulting graph becomes a valid rooted tree again. If multiple edges can be removed, we must return the one that appears last in the input.

Constraints inform us that 3 <= n <= 1000, so algorithms with time complexity O(n²) may work but are not ideal for large n. Each node label is unique and positive, and no self-loops exist. The problem guarantees exactly one extra edge, which simplifies the cases we need to consider.

Key edge cases include:

  1. A node having two parents. We must choose which edge to remove to restore the tree property.
  2. A cycle in the graph. Removing the edge that closes the cycle restores the acyclic property.
  3. A combination of both: a node has two parents, and one of the edges creates a cycle.

Approaches

Brute Force Approach

A naive approach would iterate through each edge and temporarily remove it, then check if the resulting graph is a rooted tree. To check if the graph is a rooted tree, we can use a DFS or BFS to ensure there are no cycles and each node has exactly one parent. While this approach is correct, it requires checking the tree property for every edge, resulting in O(n²) time complexity. This is inefficient for the upper bound of n = 1000.

Optimal Approach

The optimal approach leverages Union-Find (Disjoint Set Union) combined with parent tracking. The key insight is that the redundant edge can only fall into one of three categories:

  1. Node with two parents, no cycle.
  2. Node with two parents, cycle present.
  3. Cycle, no node with two parents.

First, we scan the edges to identify if a node has two parents. If it does, we temporarily ignore the second edge and check for cycles using Union-Find. If a cycle exists, the redundant edge is the first parent edge; otherwise, it is the second edge. If no node has two parents, we simply use Union-Find to detect the cycle and return the edge that completes it.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Remove each edge and check if the graph is a valid tree
Optimal O(n) O(n) Use parent array and Union-Find to efficiently detect two parents and cycles

Algorithm Walkthrough

  1. Initialize a parent array of size n+1 to keep track of each node’s parent.
  2. Initialize two variables cand1 and cand2 to store candidate edges for a node with two parents.
  3. Iterate through each edge [u, v]. If v already has a parent, store [existing_parent, v] as cand1 and [u, v] as cand2, then temporarily ignore cand2.
  4. Use Union-Find to iterate through the edges:

a. Skip cand2 if it exists.

b. For each edge [u, v], union u and v.

c. If u and v are already connected, a cycle is detected. 5. Determine which edge to remove:

a. If there is no two-parent node, return the edge that creates the cycle.

b. If a two-parent node exists and cycle is detected, return cand1.

c. If a two-parent node exists but no cycle, return cand2.

Why it works: By tracking parent relationships and detecting cycles simultaneously, we handle all scenarios of the extra edge: nodes with two parents, cycles, or both. This ensures the returned edge is exactly the one causing the violation of the rooted tree property.

Python Solution

from typing import List

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = [0] * (n + 1)
        cand1 = cand2 = None
        
        # Step 1: Check for a node with two parents
        for u, v in edges:
            if parent[v] == 0:
                parent[v] = u
            else:
                cand1 = [parent[v], v]
                cand2 = [u, v]
                # Temporarily remove the second edge
                break
        
        # Union-Find setup
        def find(x):
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]
        
        uf = list(range(n + 1))
        
        # Step 2: Detect cycle
        for u, v in edges:
            if [u, v] == cand2:
                continue
            pu, pv = find(u), find(v)
            if pu == pv:
                if cand1:
                    return cand1
                else:
                    return [u, v]
            uf[pv] = pu
        
        # Step 3: If no cycle, remove the second parent edge
        return cand2

Explanation: The first loop identifies a node with two parents. The Union-Find logic then detects cycles efficiently, skipping the second candidate if necessary. Depending on the presence of a cycle and two-parent node, we return the correct edge.

Go Solution

func findRedundantDirectedConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    var cand1, cand2 []int
    
    for _, e := range edges {
        u, v := e[0], e[1]
        if parent[v] == 0 {
            parent[v] = u
        } else {
            cand1 = []int{parent[v], v}
            cand2 = []int{u, v}
            break
        }
    }
    
    uf := make([]int, n+1)
    for i := 0; i <= n; i++ {
        uf[i] = i
    }
    
    var find func(int) int
    find = func(x int) int {
        if uf[x] != x {
            uf[x] = find(uf[x])
        }
        return uf[x]
    }
    
    for _, e := range edges {
        if cand2 != nil && e[0] == cand2[0] && e[1] == cand2[1] {
            continue
        }
        u, v := e[0], e[1]
        pu, pv := find(u), find(v)
        if pu == pv {
            if cand1 != nil {
                return cand1
            }
            return e
        }
        uf[pv] = pu
    }
    
    return cand2
}

Go-specific notes: We use slices instead of lists, nil checks for candidates, and functions are closures to handle recursive find.

Worked Examples

Example 1: [[1,2],[1,3],[2,3]]

  1. Node 3 has two parents: cand1 = [1,3], cand2 = [2,3].
  2. Union-Find:
  • [1,2]: union success
  • [1,3]: union success
  • Skip cand2 ([2,3])
  1. No cycle detected. Remove cand2 = [2,3].

Example 2: [[1,2],[2,3],[3,4],[4,1],[1,5]]

  1. No node with two parents.
  2. Union-Find:
  • [1,2], [2,3], [3,4]: union success
  • [4,1]: cycle detected. Return [4,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to detect two parents + Union-Find with path compression
Space O(n) Parent array and Union-Find array of size n+1

The Union-Find operations are near constant time due to path compression, ensuring linear time overall.

Test Cases

# Provided examples
assert Solution().findRedundantDirectedConnection([[1,2],[1,3],[2,3]]) == [2,3]  # node with two parents
assert Solution().findRedundantDirectedConnection([[1,2],[2,3],[3,4],[4,1],[1,5]]) == [4,1]  # cycle

# Edge cases
assert Solution().findRedundantDirectedConnection([[2,1],[3,1],[4,2],[1,4]]) == [2,1]  # two parents + cycle
assert Solution().findRedundantDirectedConnection([[1,2],[2,3],[3,1]]) == [3,1]  # simple cycle
assert Solution().findRedundantDirectedConnection([[1,2],[2,3],[3,4],[4,5],[5,3]]) == [5,3]  # cycle at the end
Test Why
[[1