# 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:

| Property | Meaning |
|---|---|
| One root | Exactly one node has no parent |
| One parent per non-root node | Every other node has exactly one parent |
| Reachability | Every node is reachable from the root |
| No cycle | Following directed edges never loops |

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

| Item | Meaning |
|---|---|
| Input | `edges`, a list of directed edges |
| Output | The redundant directed edge |
| Node labels | `1` through `n` |
| Edge direction | `[u, v]` means `u -> v` |
| Required result | Remove one edge to restore a rooted tree |

Example function shape:

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

## Examples

Example 1:

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

Node `3` has two parents:

```text
1 -> 3
2 -> 3
```

Removing `[2, 3]` restores the rooted tree.

Answer:

```python
[2, 3]
```

Example 2:

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

There is a directed cycle:

```text
1 -> 2 -> 3 -> 4 -> 1
```

No node has two parents.

Removing `[4, 1]` breaks the cycle.

Answer:

```python
[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:

| Failure type | Meaning |
|---|---|
| A node has two parents | Two edges point into the same node |
| A cycle exists | Directed edges form a loop |

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:

```text
1 -> 2
1 -> 3
2 -> 3
```

Node `3` has two parents: `1` and `2`.

The later incoming edge is redundant.

Answer:

```python
[2, 3]
```

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

Example:

```text
1 -> 2
2 -> 3
3 -> 1
4 -> 1
```

Node `1` has two parents: `3` and `4`.

The cycle is:

```text
1 -> 2 -> 3 -> 1
```

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

```python
[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:

```text
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:

| Situation | Return |
|---|---|
| No node has two parents, Union-Find finds a cycle | The edge that caused the cycle |
| Node has two parents, and skipping later edge removes cycle | Later edge |
| Node has two parents, and skipping later edge still leaves cycle | Earlier edge |

## 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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * α(n))` | Union-Find operations are almost constant |
| Space | `O(n)` | Parent arrays for indegree detection and Union-Find |

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

## Implementation

```python
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:

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

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

```python
candidate1 = parent_edge[v]
```

and the new edge is:

```python
candidate2 = [u, v]
```

Then we run Union-Find.

During this pass, we skip the later parent edge:

```python
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:

```python
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:

```python
return candidate2
```

means the later incoming edge was the only problem.

## Testing

```python
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:

| Test | Expected | Why |
|---|---:|---|
| `[[1,2],[1,3],[2,3]]` | `[2,3]` | Node `3` has two parents, no cycle after removing later edge |
| `[[1,2],[2,3],[3,4],[4,1],[1,5]]` | `[4,1]` | Pure cycle case |
| `[[2,1],[3,1],[4,2],[1,4]]` | `[2,1]` | Two parents and a cycle, remove earlier parent |
| `[[4,2],[1,5],[5,2],[5,3],[2,4]]` | `[4,2]` | Two-parent node participates in cycle |