Redundant Connection
In this problem, a tree is an undirected graph that is connected and has no cycles. Given a graph that started as a tree with n nodes, one edge was added. Find the edge that can be removed so that the graph is still a tree.
Examples
edges = [[1,2],[1,3],[2,3]]
[2,3]
Removing edge [2,3] leaves a valid tree.
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
[1,4]
Removing edge [1,4] leaves a valid tree.
Constraints
- •
n == edges.length - •
3 <= n <= 1000 - •
edges[i].length == 2 - •
1 <= ai < bi <= n - •
ai != bi - •
There are no repeated edges. - •
The given graph is connected.
Approaches
Try removing each edge and check if the graph is still connected.
def find_redundant_connection(edges):
def is_connected(n, edges_to_keep):
graph = [[] for _ in range(n + 1)]
for u, v in edges_to_keep:
graph[u].append(v)
graph[v].append(u)
visited = set()
stack = [1]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
stack.append(neighbor)
return len(visited) == n
n = len(edges)
for i in range(len(edges) - 1, -1, -1):
remaining = edges[:i] + edges[i+1:]
if is_connected(n, remaining):
return edges[i]
return []Use Union Find to detect the edge that creates a cycle.
def find_redundant_connection(edges):
parent = list(range(len(edges) + 1))
rank = [0] * (len(edges) + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return []Same Union Find with path compression and union by rank.
Diagram
def find_redundant_connection(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v]
parent[pu] = pv
return []Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS - Try Removing Each Edge | O(n^3) | O(n + E) | Try removing each edge and check if the graph is still connected. |
| Union Find | O(n * alpha(n)) | O(n) | Use Union Find to detect the edge that creates a cycle. |
| Optimized Union Find | O(n * alpha(n)) | O(n) | Same Union Find with path compression and union by rank. |
Try removing each edge and check if the graph is still connected.
Use Union Find to detect the edge that creates a cycle.
Same Union Find with path compression and union by rank.
Common Mistakes
Not using path compression (less efficient)
Forgetting that the redundant edge is the one that creates a cycle
Not handling the case where multiple edges could be removed