The Redundant Connection II extends Part I to directed graphs (rooted trees). A valid rooted tree has one root with no incoming edges, all others with exactly one incoming edge, and no cycles. The extra edge creates either a node with two parents, a cycle, or both. Finding the correct redundant edge requires careful case analysis. The union find, BFS, graph, and DFS interview pattern is demonstrated at an advanced level.
Meta and Google ask this hard variant because it requires handling three cases: (1) a node has two incoming edges — one must be removed, (2) a cycle exists — the cycle-creating edge must be removed, (3) both issues combined. It tests the ability to handle multiple failure modes simultaneously.
Three-case analysis + Union-Find. Find if any node has two parent edges (candidates). If yes, try removing each candidate and check if remaining graph is a valid tree (using Union-Find). If no such node, use Union-Find to find the edge creating the cycle.
edges=[(1,2),(2,3),(3,4),(4,1),(1,5)]. Node 1 has two parents: (4,1) and a hypothetical. Check candidates... Actually (4,1): 1 has incoming from 4 and no double-parent directly. But cycle: 1→2→3→4→1. Find cycle edge using Union-Find. Answer: (4,1) (last edge in cycle).
Redundant Connection II requires careful case decomposition. Always check for double-parent nodes first — they provide candidate edges. If no double-parent, find the cycle-causing edge. When both occur together, the answer is always the second parent edge (the one creating the double-parent AND is part of the cycle). Practice directed graph validation: check in-degrees and cycle detection together.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Divide Nodes Into the Maximum Number of Groups | Hard | Solve | |
| Distance to a Cycle in Undirected Graph | Hard | Solve | |
| Count the Number of Complete Components | Medium | Solve | |
| Minimum Score of a Path Between Two Cities | Medium | Solve | |
| Redundant Connection | Medium | Solve |
