685. Redundant Connection II¶
Edited by Charles
Hard · Python · Graph
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
This problem is an extension of LeetCode 684. Redundant Connection.
In LeetCode 684, the graph is undirected, so the main problem is detecting a cycle.
Original study notes follow, including intermediate snippets and earlier attempts.
Idea¶
This problem is an extension of LeetCode 684. Redundant Connection.
In LeetCode 684, the graph is undirected, so the main problem is detecting a cycle.
In this problem, the graph is directed and should originally be a rooted tree.
A valid rooted tree has two important properties:
- Every node except the root has exactly one parent.
- There is no cycle.
The graph originally contains n nodes and n - 1 edges, and then exactly one extra directed edge is added.
Therefore, the extra edge can cause two types of problems:
These two problems can also happen at the same time.
So there are three possible cases:
We first use an array:
Here, this parent represents the actual directed parent relationship in the graph.
For every directed edge:
we check whether v already has a parent.
If:
then v does not have a parent yet:
Otherwise, v already has a parent, which means we found a node with two parents.
Suppose:
and now we encounter:
Then the two candidate edges are:
where:
For example:
When processing [2, 3], we discover that 3 already has parent 1.
Therefore:
If a node has two parents, one of these two incoming edges must be removed.
So instead of checking every edge in the graph, we only need to determine:
We can determine this using Union Find.
If there is a two-parent situation, we first assume that the later edge is the redundant one.
Therefore, when processing the graph with Union Find, we temporarily skip:
If candidate2 is None, the comparison:
is simply False, so no edge will be skipped.
We use the same Union Find idea as LeetCode 684.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size + 1))
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 != root2:
self.parent[root1] = root2
def isSame(self, node1, node2):
return self.find(node1) == self.find(node2)
For each edge:
if:
is already True, then u and v are already connected.
Adding this edge creates a cycle.
Case 1: Cycle Only¶
Example:
Edges:
There is no node with two parents.
Therefore:
During Union Find, eventually we process:
At this point:
is already True.
So this edge creates the cycle.
We directly return:
In code:
Case 2: Two Parents, No Cycle¶
Example:
Edges:
Node 3 has two parents:
Therefore:
Now temporarily skip:
The remaining graph is:
There is no cycle.
Therefore, removing candidate2 successfully restores a valid rooted tree.
So:
Answer:
Case 3: Two Parents + Cycle¶
Consider:
Node 1 has two parents:
Therefore:
We first temporarily skip:
But the remaining graph contains:
There is still a cycle.
This means:
Removing
candidate2does not solve the problem.
Therefore, the edge that must be removed is:
So:
The entire problem can be summarized as:
Scan all edges
|
v
Does a node have
two parents?
/ \
No Yes
| |
| candidate1
| candidate2
| |
| Skip candidate2
| |
v v
Union Find Union Find
| |
v v
Cycle? Cycle?
| / \
| Yes No
v | |
return edge | |
v v
candidate1 candidate2
Therefore:
Case 1:
No two-parent node + cycle
→ return the cycle-producing edge
Case 2:
Two-parent node + no cycle after skipping candidate2
→ return candidate2
Case 3:
Two-parent node + cycle still exists after skipping candidate2
→ return candidate1
from typing import List
class UnionFind:
def __init__(self, size):
self.parent = list(range(size + 1))
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 != root2:
self.parent[root1] = root2
def isSame(self, node1, node2):
return self.find(node1) == self.find(node2)
class Solution:
def findRedundantDirectedConnection(
self, edges: List[List[int]]
) -> List[int]:
n = len(edges)
parent = [0] * (n + 1)
candidate1 = None
candidate2 = None
# Find whether a node has two parents
for u, v in edges:
if parent[v] == 0:
parent[v] = u
else:
candidate1 = [parent[v], v]
candidate2 = [u, v]
break
uf = UnionFind(n)
# Detect cycle while skipping candidate2
for u, v in edges:
# Skip the last redundant edge
if [u, v] == candidate2:
continue
if uf.isSame(u, v):
# Case 1: cycle only
if candidate1 is None:
return [u, v]
# Case 3: two parents + cycle
return candidate1
uf.union(u, v)
# Case 2: two parents but no cycle
return candidate2
There are two different concepts called parent in this solution.
They should not be confused.
Directed Graph Parent¶
This represents:
Its purpose is to detect:
Union Find Parent¶
Inside:
the meaning is different.
It represents the internal structure of the Disjoint Set Union.
Its purpose is to determine:
So:
The graph originally is a rooted tree.
A tree with n nodes has:
and contains no cycle.
The problem adds exactly one extra edge.
Therefore, if the extra edge creates a cycle, that cycle consists of:
A tree has exactly one path between any two connected nodes.
Therefore, one extra edge can introduce at most one cycle.
However, the extra edge does not necessarily create a cycle.
It may instead create a node with two parents.
LeetCode 684 only needs to detect:
So:
LeetCode 685 must handle:
Therefore, we first detect the two-parent situation and then use the same Union Find cycle detection from LeetCode 684.
A useful way to remember the relationship is:
LeetCode 684
|
| Cycle Detection
v
Union Find
LeetCode 685
|
+-- Detect Two Parents
|
+-- Use 684's Union Find
to Detect Cycle
Let n be the number of nodes.
We scan the edges once to detect a node with two parents:
Then we scan the edges again with Union Find:
where α(n) is the inverse Ackermann function and is effectively constant for practical input sizes.
Therefore, the overall time complexity is approximately:
Space complexity:
for the graph-parent array and the Union Find structure.
The most important thing to remember is that LeetCode 685 has three cases:
1. Cycle only
→ return the edge that creates the cycle
2. Two parents, no cycle after skipping the later edge
→ return the later parent edge
3. Two parents, cycle still exists after skipping the later edge
→ return the earlier parent edge
A compact way to remember the algorithm is:
Find two parents first
↓
candidate1 = earlier edge
candidate2 = later edge
↓
Skip candidate2
↓
Run Union Find
↓
Is there a cycle?
/ \
Yes No
| |
candidate1 candidate2
If there is no two-parent situation, simply use Union Find exactly like LeetCode 684 and return the edge that creates the cycle.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | August 25, 2026 |
Python solution¶
class UnionFind:
def __init__(self, size):
self.parent = list(range(1 + size))
def find(self, node):
if node != self.parent[node]:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 != root2:
self.parent[root2] = root1
def isSame(self, node1, node2):
return self.find(node1) == self.find(node2)
class Solution:
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
parent = [0] * (len(edges) + 1)
candidate1 = None
candidate2 = None
for u, v in edges:
if parent[v] == 0:
parent[v] = u
else:
candidate1 = [parent[v], v]
candidate2 = [u, v]
break
uf = UnionFind(len(edges))
for u, v in edges:
if candidate2 == [u, v]:
continue
if uf.isSame(u, v):
if not candidate1:
return [u, v]
return candidate1
uf.union(u, v)
return candidate2