Redundant Connection II

Problem Id: 685 Difficulty: Hard


Intuition

Solution


class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        # A tree's node has indegree 1 except for the root. So if
        # one node has indegree more then one, then there must be
        # a redundant edge to the node.
        n = len(edges)
        indegree = [0] * (n + 1)
        for p, q in edges:
            indegree[q] += 1

        if 2 in indegree:
            dest = indegree.index(2)
            candidates = [e for e in edges if e[1] == dest]
            dsu = DSU(n + 1)
            for p, q in [e for e in edges if e[1] != dest]:
                dsu.union(p, q)
            x, y = candidates[0]
            if dsu.find(x) == dsu.find(y):
                return [x, y]
            return candidates[1]

        # If all node has indegree 1, then there must be a cycle.
        # Remove any node from that cycle could work.
        dsu = DSU(n + 1)
        for p, q in edges:
            if not dsu.union(p, q):
                return [p, q]