684. Redundant Connection (Medium)
Problem
A tree on n nodes can be represented by n - 1 edges. You’re given an array of n edges such that, with one edge added, the resulting graph has exactly one cycle. Return the added edge. If multiple answers, return the one that appears last in the input.
Example
edges = [[1,2],[1,3],[2,3]]→[2, 3]edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]→[1, 4]
LeetCode 684 · Link · Medium
Approach 1: Brute force, for each edge, test if removing it makes the graph a tree
Remove each edge in turn; run a DFS/BFS on the rest; test for connectivity and acyclicity.
from collections import defaultdict
def find_redundant_connection(edges): n = len(edges) # L1: n edges, nodes 1..n
def is_tree(skip_idx): # L2: O(n) per call graph = defaultdict(list) # L3: build adjacency list for i, (u, v) in enumerate(edges): # L4: O(n) if i == skip_idx: continue graph[u].append(v) graph[v].append(u) visited = set() def dfs(node, parent): # L5: cycle-free DFS if node in visited: return False visited.add(node) for nb in graph[node]: if nb == parent: continue if nb in visited or not dfs(nb, node): return False return True if not dfs(1, -1): return False return len(visited) == n # L6: connected check
for i in range(n - 1, -1, -1): # L7: iterate last-to-first if is_tree(i): return edges[i] return []Where the time goes, line by line
Variables: V = number of vertices = len(edges), E = len(edges).
| Line | Per-call cost | Times executed | Contribution |
|---|---|---|---|
| L3-L4 (build graph) | O(V) | V (once per is_tree call) | O(V²) |
| L5 (DFS) | O(V) | V | O(V²) |
| L6 (connectivity check) | O(1) | V | O(V) |
| L7 + is_tree (outer loop) | O(V) per iteration | V | O(V²) ← dominates |
For each of the V edges we remove, we rebuild the graph and run a full DFS, both O(V). The total is O(V²).
Complexity
- Time: O(V²), driven by L7 (V iterations each triggering an O(V) is_tree call).
- Space: O(V) for the adjacency list and DFS stack.
Approach 2: DFS to find the cycle, pick the last edge on it
Build the graph incrementally. When adding an edge creates a cycle, mark it and report the last such edge.
This is really just a special case of Approach 3, with more bookkeeping.
Approach 3: Union-Find (canonical)
Process edges in order. For each (u, v): if u and v are already in the same component, this edge creates a cycle, return it. Otherwise, union them.
def find_redundant_connection(edges): n = len(edges) # L1: n edges parent = list(range(n + 1)) # L2: O(n) init, node i is its own root
def find(x): # L3: path-halving find while parent[x] != x: # L4: walk to root parent[x] = parent[parent[x]] # L5: path halving (compress by 2) x = parent[x] # L6: move up return x
def union(a, b): # L7: union two components ra, rb = find(a), find(b) # L8: find both roots if ra == rb: # L9: same component = cycle return False parent[ra] = rb # L10: merge return True
for u, v in edges: # L11: process each edge if not union(u, v): # L12: cycle detected return [u, v] return []Where the time goes, line by line
Variables: V = number of vertices = len(edges), E = len(edges).
| Line | Per-call cost | Times executed | Contribution |
|---|---|---|---|
| L2 (init parent) | O(V) | 1 | O(V) |
| L4-L6 (find, path-halving) | O(α(V)) amortized | 2 per edge = 2V | O(V · α(V)) |
| L9 (same-component test) | O(1) | V | O(V) |
| L10 (merge) | O(1) | up to V - 1 | O(V) |
| L11-L12 (edge loop + union) | O(α(V)) per edge | V | O(V · α(V)) ← dominates |
The α(V) factor is the inverse Ackermann function, which grows so slowly it is effectively constant for all practical V (α(V) ≤ 4 for V up to 10^80). Path halving at L5 keeps the tree nearly flat: each find traverses at most a logarithmic height that collapses on subsequent calls. The amortized cost per operation is O(α(V)), giving O(V · α(V)) total, essentially linear.
Complexity
- Time: O(V · α(V)) ≈ O(V), driven by L11-L12 (V union operations each costing O(α(V)) amortized).
- Space: O(V) for the parent array.
Why this works
If the graph has exactly one cycle, then exactly one edge causes a “same-component” event when processed in order. All edges preceding it form a forest; this edge closes a cycle. Since input is a tree plus one edge, that closing edge is the answer.
Summary
| Approach | Time | Space |
|---|---|---|
| Per-edge removal + tree check | O(V²) | O(V) |
| Cycle-finding DFS | O(V) | O(V) |
| Union-Find | O(V · α(V)) | O(V) |
Union-Find is the canonical solution and the template for any incremental connectivity problem.
Test cases
# Quick smoke tests, paste into a REPL or save as test_684.py and run.# Uses the canonical implementation (Approach 3, Union-Find).
def find_redundant_connection(edges): n = len(edges) parent = list(range(n + 1))
def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def union(a, b): ra, rb = find(a), find(b) if ra == rb: return False parent[ra] = rb return True
for u, v in edges: if not union(u, v): return [u, v] return []
def _run_tests(): # LeetCode example 1 assert find_redundant_connection([[1,2],[1,3],[2,3]]) == [2, 3]
# LeetCode example 2 assert find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]]) == [1, 4]
# Smallest possible cycle (two nodes, two edges between them) assert find_redundant_connection([[1,2],[1,2]]) == [1, 2]
# Last edge is redundant assert find_redundant_connection([[1,2],[2,3],[1,3]]) == [1, 3]
# Longer chain with cycle at end assert find_redundant_connection([[1,2],[2,3],[3,4],[4,5],[3,5]]) == [3, 5]
print("all tests pass")
if __name__ == "__main__": _run_tests()Related data structures
- Graphs, union-find for cycle detection in undirected graphs