684. Redundant Connection

Information

  • Diffculty: Medium

  • Created: 2019-09-22 02:02:26

  • Last Motified: 2019-09-22 02:02:26

Solution

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        queue = Queue()
        links = defaultdict(list)
        for n1, n2 in edges:
            links[n1].append(n2)
            links[n2].append(n1)

        marked = set()
        queue.put(edges[0][0])
        marked.add(edges[0][0])
        cp = None

        while not queue.empty():
            c = 0
            node = queue.get()
            for n in links[node]:
                if n in marked:
                    c += 1
                    if c >= 2:
                        cp = node
                    continue
                marked.add(n)
                queue.put(n)

        cycle = set()
        visited = set()
        def traverse(node):
            if node == cp:
                cycle.add(node)
                return True
            if node in visited:
                return False
            visited.add(node)
            c = 0
            for neighbour in links[node]:
                if traverse(neighbour):
                    c += 1
            if c == 1:
                cycle.add(node)
                return True
            elif c == 2:
                cycle.add(node)
            return False
        traverse(edges[0][0])

        for n1, n2 in edges[::-1]:
            if n1 in cycle and n2 in cycle:
                return [n1, n2]