Redundant Connection
You are given a tree with n nodes labeled from 1 to n, with one additional edge added to it. This extra edge creates a cycle in the graph.
Your task is to find the edge that, if removed, will make the graph a tree again.
Return the edge that can be removed to eliminate the cycle. If there are multiple answers, return the one that appears last in the input list.
Example
Input: edges = [[1,2], [1,3], [2,3]] 1 / \ 2---3 Output: [2,3]
Disjoint Set Union Approach
We use Union-Find (Disjoint Set Union) to efficiently detect cycles in an undirected graph. Since the original graph is a tree (connected and acyclic), adding one extra edge creates exactly one cycle. Union-Find helps us track which nodes are connected. If we try to connect two nodes that are already part of the same set (i.e., have the same root), it means adding this edge would form a cycle, so it must be the redundant edge.
Algorithm
-
Initialize a
dsuarray where each node is its own parent. -
For each edge
[u, v]:
-
Use
Find(x)to get the root parent of bothuandv. -
If roots are the same → cycle detected → return
[u, v]as the redundant edge. -
If roots are different → use
Union(x, y)to merge the sets.
- Return the first edge that forms a cycle.
from typing import List
def redundant_connection(edges: List[List[int]]) -> List[int]:
dsu = [i for i in range(len(edges)+1)]
def find(x):
while x!=dsu[x]:
x = dsu[x]
return x
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
dsu[rooty] = rootx
return False
else:
return True
for u, v in edges:
if union(u, v):
return [u, v]Time Complexity: O(N * α(N)), where N is the number of edges and α(N) is the inverse Ackermann function (very slow-growing, practically ≤ 5).
Each find and union operation takes nearly constant time due to path compression and union by rank (if implemented).
Space Complexity: O(N) for the dsu (disjoint set union) array to store parent links for each node.