> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.
> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.
# Redundant Connection II Python Solution
> Tested Python solution for LeetCode 685 with 20 pytest cases. Generate a practice environment with lcpy.
LeetCode 685, [Hard](/catalog/hard). Topics: [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Union-Find](/catalog/topics/union-find), [Graph Theory](/catalog/topics/graph-theory). [View on LeetCode](https://leetcode.com/problems/redundant-connection-ii/description/).
Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:
```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 685 # by problem number
lcpy gen -s redundant_connection_ii # by problem name
```
## Problem
In this problem, a rooted tree is a **directed** graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with `n` nodes (with distinct values from `1` to `n`), with one additional directed edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed.
The resulting graph is given as a 2D-array of `edges`. Each element of `edges` is a pair \[u\i\, v\i\] that represents a **directed** edge connecting nodes u\i\ and v\i\, where u\i\ is a parent of child v\i\.
Return *an edge that can be removed so that the resulting graph is a rooted tree of* `n` *nodes*. If there are multiple answers, return the answer that occurs last in the given 2D-array.
### Examples
```
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
```
```
Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]
```
### Constraints
* n == edges.length
* 3 \<= n \<= 1000
* edges\[i].length == 2
* 1 \<= u\i\, v\i\ \<= n
* u\i\ != v\i\
## Solution
Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/redundant_connection_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/redundant_connection_ii/test_solution.py):
```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
# Time: O(n * alpha(n))
# Space: O(n)
def find_redundant_directed_connection(self, edges: list[list[int]]) -> list[int]:
n = len(edges)
parent = list(range(n + 1))
dsu = list(range(n + 1))
candidate_first: list[int] | None = None
candidate_last: list[int] | None = None
cycle_edge: list[int] | None = None
def find(node: int) -> int:
while dsu[node] != node:
dsu[node] = dsu[dsu[node]]
node = dsu[node]
return node
for u, v in edges:
if parent[v] != v:
candidate_first = [parent[v], v]
candidate_last = [u, v]
continue
parent[v] = u
root_u, root_v = find(u), find(v)
if root_u == root_v:
cycle_edge = [u, v]
else:
dsu[root_u] = root_v
if candidate_first is None:
assert cycle_edge is not None
return cycle_edge
if cycle_edge is not None:
return candidate_first
assert candidate_last is not None
return candidate_last
```
## Complexity
| Time | Space |
| - | - |
| O(n \* alpha(n)) | O(n) |
## Tags
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.