Redundant Connection II: Directed Graph Cycle Detection

You are given a rooted tree that originally had n nodes labeled 1 through n, with exactly n - 1 directed edges (parent to child). One additional directed edge was added. Return the edge that, when removed, restores the tree. If there are multiple answers, return the one that appears last in the input.

This is LeetCode 685: Redundant Connection II, and it is significantly harder than its undirected cousin (problem 684). The directed edges create three distinct cases you need to handle, and missing any one of them means a wrong answer.

Case: Two parents, no cycle

Node 3 receives edges from both 1 and 4.

Remove the later edge [4, 3].

Case: Cycle, no two parents

Edge [3, 1] creates a cycle in the directed graph.

Remove the cycle-causing edge [3, 1].

Why this problem matters

Redundant Connection II forces you to think about directed graph structure in a way that simpler graph problems do not. In an undirected graph, an extra edge always creates a cycle, and you just need union-find to detect it. In a directed graph, an extra edge can cause two different problems: a node with two parents, a cycle, or both at the same time.

This problem teaches you to combine two techniques (parent tracking and union-find) and reason about multiple cases. That kind of case analysis shows up constantly in real interviews, where the hard problems are hard precisely because they have several sub-cases that each require different handling.

The three cases

Adding one directed edge to a valid rooted tree creates exactly one of these situations:

Case 1: A node has two parents, and there is no cycle. Two edges point to the same node. One of them is redundant. Remove the edge that appears later in the input.

Case 2: There is a cycle, and no node has two parents. The extra edge creates a directed cycle. This happens when the extra edge points from a descendant back to an ancestor. Use union-find to find the cycle-causing edge.

Case 3: A node has two parents, and there is also a cycle. This is the trickiest case. One of the two edges pointing to the double-parent node is part of the cycle. You must remove that specific edge, not necessarily the later one.

The key insight

Handle the two-parent check first, then use union-find. Here is the strategy:

1. Scan all edges. Track each node's parent. If any node gets a second parent, record both edges as candidate1 (the first edge) and candidate2 (the second edge).
2. If there are two candidates, temporarily remove candidate2 and run union-find on the remaining edges. If the remaining edges form a valid tree (no cycle), then candidate2 was the problem. If a cycle still exists, then candidate1 is the edge to remove (it is the one participating in the cycle).
3. If no node has two parents, just run union-find on all edges. The edge that creates a cycle is the answer.

def find_redundant_directed_connection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = [0] * (n + 1)
    candidate1 = candidate2 = None

    for u, v in edges:
        if parent[v] != 0:
            candidate1 = [parent[v], v]
            candidate2 = [u, v]
        else:
            parent[v] = u

    root = list(range(n + 1))

    def find(x: int) -> int:
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for u, v in edges:
        if candidate2 and [u, v] == candidate2:
            continue
        ru, rv = find(u), find(v)
        if ru == rv:
            if candidate1:
                return candidate1
            return [u, v]
        root[rv] = ru

    return candidate2

How the solution works

The algorithm has two phases.

Phase 1: Find the two-parent node. We scan through the edges and track parent[v] for each destination node v. When we encounter a node v that already has a parent, we know v has two incoming edges. We save both: candidate1 is the earlier edge, and candidate2 is the later one. We do not add candidate2 to the parent map.

Phase 2: Union-find to detect cycles. We process all edges (skipping candidate2 if it exists) through union-find. If we find a cycle:

• If we had two candidates, the cycle exists even without candidate2, so candidate1 must be the edge causing trouble. Return candidate1.
• If we had no candidates, we are in case 2 (pure cycle). Return the cycle-causing edge.

If we process all edges without finding a cycle, then removing candidate2 was the right choice. Return candidate2.

Step-by-step walkthrough

Let's trace through the algorithm with edges [[1,2],[1,3],[2,3]]:

Complexity analysis

Time: We scan all n edges twice, once for parent detection and once for union-find. Each union-find operation takes amortized O(alpha(n)) time with path compression, where alpha is the inverse Ackermann function. This is effectively O(n).

Space: We store the parent array and the root array, each of size n + 1. Total O(n).

The building blocks

This problem combines two fundamental techniques that CodeBricks drills independently:

1. Union-Find with path compression

The core data structure for detecting cycles in graphs:

root = list(range(n + 1))

def find(x: int) -> int:
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x

Union-find tracks connected components. When you try to union two nodes that already share the same root, you have found a cycle. Path compression (root[x] = root[root[x]]) flattens the tree on each lookup, keeping operations near O(1). This same building block appears in Redundant Connection and many other graph connectivity problems.

2. Directed graph parent tracking

Tracking incoming edges to detect structural violations:

parent = [0] * (n + 1)
for u, v in edges:
    if parent[v] != 0:
        # v has two parents
    else:
        parent[v] = u

In a valid rooted tree, every node except the root has exactly one parent. When a node has two incoming edges, you know one of them is redundant. The question is which one. This parent-tracking scan is a pattern you can reuse any time you need to validate directed tree structure.

3. Case-based reasoning in graph problems

The hardest part of this problem is not the code. It is identifying the three cases and handling each one correctly. Many hard graph problems follow this pattern: you cannot write one clean loop that handles everything. You need to break the problem into cases, handle each one, and prove that your cases are exhaustive. Practice identifying and separating cases before you start coding.

Edge cases

• The root gets a second parent. An edge points to the root from one of its descendants, creating a cycle through the root. This is case 3: two parents plus a cycle. Your algorithm must return candidate1, the edge that participates in the cycle.
• The redundant edge is the very first edge. If the first edge in the input is the redundant one, your parent tracking still works because when the second edge arrives, it flags the two-parent situation. The order of candidate1 and candidate2 depends on input order, and the union-find phase resolves which to remove.
• Linear chain with a back edge. Edges like [[1,2],[2,3],[3,1]] form a simple cycle with no two-parent node. This is pure case 2. Union-find on all edges catches [3,1] as the cycle-causing edge.
• Star graph with extra edge. A root with many children, plus an edge between two children. One child gets two parents. This is case 1 (two parents, no cycle). Return the later of the two edges pointing to that child.
• n = 2. The smallest possible input. Two edges, one node gets two parents. One edge is redundant.

From understanding to recall

You have walked through the three cases, the two-phase algorithm, and the union-find logic. The cases make sense when you read them. But in an interview, you need to remember all three cases, set up the parent scan, handle the candidate tracking, write union-find with path compression, and wire the case logic together. That is a lot of moving parts to reconstruct under pressure.

Spaced repetition bridges the gap between understanding and fluency. You practice writing the parent detection loop and the union-find cycle check from scratch at increasing intervals. After a few rounds, you do not need to re-derive the case analysis. Your hands just write it. The three cases become as automatic as the union-find template itself.

Hard problems like this one are where spaced repetition pays off the most. The logic is not complex for any single piece, but combining the pieces correctly requires practice. Drill each building block separately, then combine them until the full solution flows out naturally.

Related posts

• Redundant Connection - The undirected version of this problem, where union-find alone is enough to find the cycle-causing edge
• Course Schedule - Directed graph cycle detection using DFS, teaching the topological sort pattern that complements union-find
• Number of Islands - The essential grid DFS problem, building the graph traversal intuition that makes directed graph problems more approachable

CodeBricks breaks Redundant Connection II into its union-find, parent-tracking, and case-analysis building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a hard directed graph problem shows up in your interview, you do not scramble to remember the cases. You just write them.