Redundant Connection II

Problem

A data-center provisioning log records the directed edges that were applied to build a server hierarchy: n servers, n recorded edges - one too many, because a healthy hierarchy is a rooted tree with exactly n-1. The defect is one edge whose removal leaves every server with at most one parent, exactly one root, and no cycles. Find that edge; if multiple edges could serve, the one appearing last in the log is preferred (the case analysis guarantees uniqueness here).

Example 1:

Input: edges = [[1,2],[2,3],[3,1]]
Output: [3,1]
Explanation: no node has two parents; the edges form the cycle 1 -> 2 -> 3 -> 1, so the last edge that closes it is the defect.

Example 2:

Input: edges = [[2,1],[3,1],[2,3]]
Output: [3,1]
Explanation: node 1 has two parents (2 and 3); skipping the later edge [3,1] leaves a valid rooted tree, so it is the defect.

Example 3:

Input: edges = [[2,1],[1,3],[3,2],[4,1]]
Output: [2,1]
Explanation: node 1 has two parents (2 and 4), and skipping [4,1] still leaves the cycle 1 -> 3 -> 2 -> 1 - the cycle runs through the first parent edge [2,1], so that edge is the defect.

Constraints:

• n == edges.length
• 2 <= n <= 10^4
• edges[i] = [u, v] records a directed edge u -> v; nodes are labeled 1..n.
• Every node except the root has exactly one parent in the intended tree; the input contains exactly one defect edge.

Example 3 walk:
edges: 2->1, 1->3, 3->2, 4->1
node 1 has parents {2 (edge 0), 4 (edge 3)} -> cand_a = edge 0, cand_b = edge 3
skip edge 3, union the rest: 2->1, 1->3, 3->2 closes a cycle -> cand_a's edge [2,1] is the answer

Solution Breakdown

Approach - classify the defect (double parent, cycle, or both), then let a skip-one union pass pick the offending edge.

Direction adds a failure mode the undirected version never has: a node with two parents is broken even with zero cycles. So the first pass scans in-degrees - heads[v] remembers the index (plus one, so 0 means unset) of the first edge entering v, and a second edge into the same v marks the two candidates: cand_a (the first-parent edge) and cand_b (the second). With the scan done, three cases. No double parent: the defect is a plain cycle - run the undirected union-find pass and return the first edge that reconnects components. Double parent, and skipping cand_b leaves no cycle: the second edge was the only defect - return edges[cand_b]. Double parent, and a cycle survives without cand_b: the cycle necessarily passes through cand_a (the conflicting node is reachable cyclically from its first-parent side), and removing any other cycle edge would still leave two parents on the node - so the answer is edges[cand_a].

The skip-one union pass is what makes the case test cheap: union_pass(skip) runs find with path halving over all edges except the skip index and reports the first index whose endpoints already share a root (a cycle), or -1 (clean). Trace [[2,1],[1,3],[3,2],[4,1]]: node 1 receives 2->1 (edge 0) then 4->1 (edge 3), so cand_a = 0, cand_b = 3; skipping edge 3, the remaining edges 2->1, 1->3, 3->2 close a cycle - case three fires, answer [2,1], and brute-force confirms removing it (and only it) leaves a rooted tree. Trace [[2,1],[4,1],[1,3],[3,2]]: node 1's parents are 2 and 4; skipping [4,1] leaves 2->1, 1->3, 3->2 - still the cycle 1 -> 3 -> 2 -> 1 - so case three fires and cand_a [2,1] is the answer.

Edge cases - the pure-cycle case degenerates to the undirected problem ([[1,2],[2,3],[3,1]] -> [3,1]); the double-parent-no-cycle case is the second example ([[2,1],[3,1],[2,3]] -> [3,1]); the constraints guarantee exactly one defect, so exactly one case branch fires.

Complexity - O(n * alpha(n)) time across at most three linear edge passes (in-degree scan, union pass, and the second pass for the no-double-parent case), each union-find operation effectively constant; O(n) space for the parent and heads arrays. The undirected version is one pass - the extra passes are the price of the direction constraint.