LeetCode 685: Redundant Connection II

Problem Restatement

We are given a directed graph that started as a rooted tree with n nodes.

A rooted tree has these properties:

Then one extra directed edge was added.

We need to return one edge that can be removed so the graph becomes a rooted tree again. If multiple answers are possible, return the one that appears last in the input. The input edge [u, v] means u is the parent of v. The official constraints include n == edges.length, node labels from 1 to n, and 3 <= n <= 1000.

Input and Output

Example function shape:

def findRedundantDirectedConnection(edges: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

edges = [[1, 2], [1, 3], [2, 3]]

Node 3 has two parents:

1 -> 3
2 -> 3

Removing [2, 3] restores the rooted tree.

Answer:

[2, 3]

Example 2:

edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]

There is a directed cycle:

1 -> 2 -> 3 -> 4 -> 1

No node has two parents.

Removing [4, 1] breaks the cycle.

Answer:

[4, 1]

First Thought: Remove Each Edge and Check

A direct solution is:

1. Remove each edge one at a time.
2. Check whether the remaining graph is a valid rooted tree.
3. Return the last edge that works.

This is correct, but it is more work than needed.

A valid rooted tree fails here for one of two reasons:

The added edge can create either problem, or both.

Key Insight

There are three possible cases.

Case 1: A Node Has Two Parents, No Cycle

Example:

1 -> 2
1 -> 3
2 -> 3

Node 3 has two parents: 1 and 2.

The later incoming edge is redundant.

Answer:

[2, 3]

Case 2: A Node Has Two Parents and There Is a Cycle

Example:

1 -> 2
2 -> 3
3 -> 1
4 -> 1

Node 1 has two parents: 3 and 4.

The cycle is:

1 -> 2 -> 3 -> 1

Here the edge causing the cycle is the earlier parent edge:

[3, 1]

Removing the later edge [4, 1] would still leave the cycle.

Case 3: No Node Has Two Parents, But There Is a Cycle

Example:

1 -> 2 -> 3 -> 4 -> 1

No node has indegree 2.

The redundant edge is the edge that closes the cycle while processing edges in order.

Algorithm

First, detect whether any node has two parents.

Create a parent_edge array.

When reading edge [u, v]:

• if v has no parent yet, record [u, v]
• if v already has a parent, we have two candidate edges:
  • candidate1: the earlier parent edge
  • candidate2: the later parent edge

Then run Union-Find over all edges, but skip candidate2 if it exists.

Why skip candidate2?

Because if removing the later parent edge makes the graph a valid tree, then candidate2 is the answer.

If a cycle still exists after skipping candidate2, then the earlier parent edge candidate1 must be removed.

The decision rule is:

Correctness

If no node has two parents, then the only possible violation is a cycle.

Union-Find detects the first edge whose endpoints are already connected in the underlying undirected sense. In this case, that edge is the redundant edge that closes the cycle, so returning it is correct.

If a node has two parents, call the two incoming edges candidate1 and candidate2, where candidate1 appears earlier and candidate2 appears later.

Any valid rooted tree can keep only one of these two edges, because a non-root node may have exactly one parent.

The algorithm first tries skipping candidate2.

If no cycle appears, then the remaining graph has n - 1 edges, no two-parent node, and no cycle. It is a rooted tree, so removing candidate2 is correct. This also satisfies the rule to return the later edge when both are valid.

If a cycle still appears while candidate2 is skipped, then removing candidate2 does not fix the graph. The extra edge must be candidate1, because the cycle uses the earlier incoming edge. Removing candidate1 both removes the two-parent conflict and breaks the cycle.

Therefore, the algorithm returns exactly the edge whose removal restores a rooted tree.

Complexity

Let n = len(edges).

α(n) is the inverse Ackermann function. In practice, this behaves like linear time.

Implementation

class Solution:
    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)

        parent_edge = [None] * (n + 1)
        candidate1 = None
        candidate2 = None

        for u, v in edges:
            if parent_edge[v] is None:
                parent_edge[v] = [u, v]
            else:
                candidate1 = parent_edge[v]
                candidate2 = [u, v]
                break

        parent = list(range(n + 1))

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            parent[root_a] = root_b
            return True

        for u, v in edges:
            if candidate2 is not None and [u, v] == candidate2:
                continue

            if not union(u, v):
                if candidate1 is not None:
                    return candidate1

                return [u, v]

        return candidate2

Code Explanation

We first scan edges to find whether any node has two parents:

parent_edge = [None] * (n + 1)
candidate1 = None
candidate2 = None

If a child v already has a parent, then the old edge is:

candidate1 = parent_edge[v]

and the new edge is:

candidate2 = [u, v]

Then we run Union-Find.

During this pass, we skip the later parent edge:

if candidate2 is not None and [u, v] == candidate2:
    continue

If skipping it avoids all cycles, then candidate2 is the edge to remove.

If Union-Find still finds a cycle:

if not union(u, v):

then we return candidate1 if a two-parent case exists.

Otherwise, this is the pure cycle case, so we return the current edge.

At the end:

return candidate2

means the later incoming edge was the only problem.

Testing

def run_tests():
    s = Solution()

    assert s.findRedundantDirectedConnection(
        [[1, 2], [1, 3], [2, 3]]
    ) == [2, 3]

    assert s.findRedundantDirectedConnection(
        [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
    ) == [4, 1]

    assert s.findRedundantDirectedConnection(
        [[2, 1], [3, 1], [4, 2], [1, 4]]
    ) == [2, 1]

    assert s.findRedundantDirectedConnection(
        [[4, 2], [1, 5], [5, 2], [5, 3], [2, 4]]
    ) == [4, 2]

    print("all tests passed")

run_tests()

Test meaning: