Problem Statement
Redundant Connection II
A rooted tree here means a family tree drawn with arrows. Every node has exactly one arrow pointing into it from its parent, except the very top node (the root) which has no parent. The arrows all flow downward from that single root. We are given such a tree, but someone added one extra arrow by mistake. That extra arrow breaks the rules in one of three ways: (1) some node now has two arrows pointing into it, so it has two parents, and there is no loop, (2) the arrows form a loop where you can follow them around and end up back where you started, but no node has two parents, or (3) both problems happen at once, a node with two parents and a loop. Our job is to find the one arrow we can delete to make it a valid rooted tree again. We solve all three cases with one tool called Union-Find.
Signals to notice
Brute force first
Try removing each edge — O(E × (V+E)).
The key insight
Track double-parent nodes. If found, one of the two parent edges is redundant. Use Union-Find for cycle detection. Handle three cases: double parent only, cycle only, both. O(V × α(V)).
Trace it on edges=[[1,2],[2,3],[3,1],[4,1]]
Pass1 [1,2]: v=2 unseen -> parent_map={2:1}
Pass1 [2,3]: v=3 unseen -> parent_map={2:1,3:2}
Pass1 [3,1]: v=1 unseen -> parent_map={2:1,3:2,1:3}
Pass1 [4,1]: v=1 seen -> cand1=[3,1], cand2=[4,1]
Pass2 [1,2]: find(1)=1,find(2)=2 differ -> union uf[2]=1
Pass2 [2,3]: find(2)=1,find(3)=3 differ -> union uf[3]=1
Pass2 [3,1]: find(3)=1,find(1)=1 EQUAL -> cycle; cand1 set -> return [3,1]
Answer = [3,1]What must stay true
Extra edge causes either double parent, cycle, or both. Careful case analysis identifies which edge to remove.
Shape of the loop
for (u,v) in edges: # pass 1: spot a node with 2 parents
if v already has a parent: cand1=[oldParent,v]; cand2=[u,v]
else record parent of v
for (u,v) in edges: # pass 2: union-find, skipping cand2
if [u,v]==cand2: continue
if find(u)==find(v): return cand1 or [u,v] # cycle found
union(u,v)
return cand2 # no cycle -> drop the 2nd parent edgePseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not handling all three cases — when both double-parent and cycle occur, the overlapping edge is the answer.