Redundant Connection II — Solution

Problem

You have a directed graph with n nodes built by taking a rooted tree and adding one extra directed edge. Given all n edges, find the edge that, when removed, turns the graph back into a valid rooted directed tree (where every non-root node has exactly one parent and all nodes are reachable from the root).

• Input: [[1,2],[1,3],[2,3]]
• Output: [2,3]
• Explanation: Removing [2,3] leaves edges 1→2 and 1→3, which form a valid tree rooted at 1.

Counter-example: [[2,1],[3,1],[4,2],[1,4]] → Output: [2,1] (not [3,1]), because even after removing [3,1], the cycle 1→4→2→1 remains. The edge that breaks both the double-parent and the cycle is [2,1].

Intuition

Adding one edge to a valid rooted directed tree can only cause two kinds of trouble: a node gains a second parent (in-degree 2), or a cycle forms while every node still has exactly one parent. In the first case, one of the two competing parent edges is the culprit — specifically the one whose removal leaves a cycle-free tree. In the second case, the culprit is simply the edge that closes the cycle.

Solution — Union-Find with Case Analysis

Scan edges first to detect any node with two parents, recording both candidate edges. Then run Union-Find on all edges while skipping the second candidate. If Union-Find finds a cycle, the second candidate is innocent and the first is the answer; otherwise the second candidate itself is the answer.

1. Walk all edges and track the first parent of each node. When a node gets a second parent, store the first parent edge as edge1 and the second as edge2.
2. Initialize Union-Find over n nodes.
3. Walk all edges again, skipping edge2 if it exists. Use union(u, v) to merge components.
4. If union(u, v) would create a cycle (u and v already share a root):
   • If no double-parent was found → return the current cycle-forming edge.
   • If a double-parent was found → edge2 is innocent; return edge1.
5. If the full pass completes without a cycle → edge2 is the intruder; return edge2.

1def findRedundantDirectedConnection(edges: list[list[int]]) -> list[int]:
2    n = len(edges)
3    uf_parent = list(range(n + 1))
4
5    def find(x: int) -> int:
6        while uf_parent[x] != x:
7            uf_parent[x] = uf_parent[uf_parent[x]]  # path halving
8            x = uf_parent[x]
9        return x
10
11    def union(x: int, y: int) -> bool:
12        root_x, root_y = find(x), find(y)
13        if root_x == root_y:
14            return False  # already connected — adding this edge creates a cycle
15        uf_parent[root_x] = root_y
16        return True
17
18    # track which node each child's parent is; detect double-parent
19    tree_parent = [0] * (n + 1)
20    edge1 = edge2 = None
21
22    for u, v in edges:
23        if tree_parent[v] == 0:
24            tree_parent[v] = u
25        else:
26            edge1 = [tree_parent[v], v]  # first edge that pointed to v
27            edge2 = [u, v]               # second edge — the later candidate
28
29    for u, v in edges:
30        if [u, v] == edge2:
31            continue  # skip the second candidate to test whether edge1 is in a cycle
32        if not union(u, v):
33            # cycle detected during Union-Find pass
34            if edge1 is None:
35                return [u, v]  # no double-parent case — this edge closes the cycle
36            return edge1       # double-parent case — edge2 was innocent, edge1 is in the cycle
37    return edge2               # no cycle without edge2 — edge2 itself is the intruder

Time: O(n · α(n)) — one pass to find the double-parent candidate, one Union-Find pass; α(n) is the inverse-Ackermann factor from path compression.

Space: O(n) — Union-Find parent array plus the tree-parent tracking array.

Complexity Summary

Common Mistakes

• Handling only the cycle case: Treating this like Redundant Connection I (undirected) ignores the possibility that the extra edge gives a node two parents without creating a cycle, producing the wrong candidate.
• Skipping the wrong candidate during Union-Find: The pass must skip edge2 (the later of the two parent edges), not edge1. Skipping edge1 would cause the test to miss the cycle that implicates edge1.
• Returning edge2 when Union-Find finds a cycle: If a cycle appears while running without edge2, it means edge2 is innocent — edge1 must be the answer. A common mistake is returning edge2 in this branch.
• Forgetting that both a cycle and a double-parent can coexist: When the double-parent node is also inside a cycle, the answer is always edge1 (the first parent edge), not edge2. The counter-example in the problem statement ([[2,1],[3,1],[4,2],[1,4]]) demonstrates this.
• Comparing edge objects by reference: In languages where edge == edge2 compares references (not values), the skip check silently fails and Union-Find processes edge2, corrupting the result. Always compare element-wise.

Related Problems

• course-schedule — directed cycle detection using DFS or topological sort
• number-of-provinces — Union-Find on an undirected graph to count connected components
• find-if-path-exists-in-graph — basic graph connectivity using Union-Find or BFS
• evaluate-division — weighted Union-Find on a directed graph for ratio queries
• clone-graph — full graph traversal with node identity tracking