Python BFS, Kahn's algorithm and Time Complexity O(N)
Intuition\n Describe your first thoughts on how to solve this problem. \nUse Kahn\'s algorithm to drop out each node with indegree == 1, and check the first edg
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse Kahn\'s algorithm to drop out each node with indegree == 1, and check the first edge with both indegree == 2.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build a undirected graph and indegree\n2. Find initial value of queue for dropping out\n3. Do BFS and drop out each neighboring node with indegree == 1\n4. There are a cycle in remaining nodes, and check each edge from the end with \n```\nindegree[a] == 2 and indegree[b] and return [a, b]\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(|V|+|E|) = O(N), N is number of edges\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(|V|+|E|) = O(N)\n# Code\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        # drop out indegree == 1, and check from the bottom return first indegree==2\n        n = len(edges)\n        indegree = collections.defaultdict(int) # SC: O(|V|)\n        graph = collections.defaultdict(list) # SC: O(|V|+|E|)\n        for a,b in edges:\n            graph[a].append(b)\n            graph[b].append(a)\n            indegree[a] += 1\n            indegree[b] += 1\n        # find indegree == 1\n        queue = collections.deque([i for i,v in indegree.items() if v==1])\n        while queue: # TC: O(|V|+|E|), explore all vertices and edges\n            node = queue.popleft()\n            indegree[node] -= 1\n            for nei in graph[node]:\n                indegree[nei] -= 1\n                if indegree[nei] == 1:\n                    queue.append(nei)\n        # find first indegree == 2 edges from the end\n        for a, b in edges[::-1]:\n            if indegree[a] == 2 and indegree[b]:\n                return [a,b]\n\n```
['Breadth-First Search', 'Graph', 'Python3']