Redundant Connection II
hardTime: O(n)Space: O(n)
Recognize the pattern
redundant edge in directed rooted treetwo parents or cyclecase analysis
Brute force idea
Try removing each edge — O(E × (V+E)).
Better approach
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)).
Key invariant
Extra edge causes either double parent, cycle, or both. Careful case analysis identifies which edge to remove.
Watch out for
Not handling all three cases — when both double-parent and cycle occur, the overlapping edge is the answer.