Redundant Connection II
hardTime: O(n)Space: O(n)
Signals to notice
redundant edge in directed rooted treetwo parents or cyclecase analysis
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)).
What must stay true
Extra edge causes either double parent, cycle, or both. Careful case analysis identifies which edge to remove.
Easy way to go wrong
Not handling all three cases — when both double-parent and cycle occur, the overlapping edge is the answer.