Redundant Connection II

Intuition

Adding one edge to a rooted tree breaks it in exactly one of two ways: some node gains a second parent, or a cycle appears, or both happen at once. First we scan for a node with two incoming edges and remember the earlier candidate A and the later candidate B. Then we union all edges except B (if B exists) and watch for a cycle. If a cycle still forms without B, then B was innocent and the real culprit is A; if no cycle forms, B was the redundant edge. When there is no two-parent conflict at all, the extra edge simply closed a cycle, so the edge that triggers the union conflict is the answer. Processing edges in order and preferring the later candidate handles the tie-breaking rule automatically.

Algorithm walkthrough

1. 1Scan the edges tracking each node's incoming edge index; if a node already has a parent, record candidate A (earlier edge) and candidate B (current edge).
2. 2Initialize a union-find structure over nodes 1..n with path compression.
3. 3Iterate the edges again, skipping candidate B if it exists, and try to union each edge's endpoints.
4. 4If two endpoints already share a root, a cycle exists: return candidate A when a two-parent conflict was found, otherwise return this cycle-closing edge.
5. 5If the loop finishes without any cycle, the skipped candidate B is the redundant edge.
6. 6Return the identified edge, which is guaranteed to be the last valid removable edge.

Implementation

from typing import List

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent_edge = [-1] * (n + 1)
        cand1 = -1
        cand2 = -1
        for i in range(n):
            v = edges[i][1]
            if parent_edge[v] != -1:
                cand1 = parent_edge[v]
                cand2 = i
            else:
                parent_edge[v] = i

        uf = list(range(n + 1))

        def find(x: int) -> int:
            while uf[x] != x:
                uf[x] = uf[uf[x]]
                x = uf[x]
            return x

        for i in range(n):
            if i == cand2:
                continue
            u, v = edges[i]
            ru, rv = find(u), find(v)
            if ru == rv:
                return edges[cand1] if cand1 != -1 else edges[i]
            uf[rv] = ru

        return edges[cand2]