https://leetcode.com/problems/critical-connections-in-a-network/submissions/

criticalConnectionsInANetwork.py

from collections import deque

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        
        results = []
        
        graph = {}
        
        for a, b in connections:
            if a not in graph:
                graph[a] = set()
            if b not in graph:
                graph[b] = set()
            graph[a].add(b)
            graph[b].add(a)
            
        # make sure there's at least an empty set for every node
        # in case some nodes begin isolated
        for i in range(n):
            if i not in graph:
                graph[i] = set()
        
        for i in range(len(connections)):
            if not self.canConnectAllWithout(connections[i][0], connections[i][1], graph, n):
                results.append(connections[i])
                
        return results
    
    def canConnectAllWithout(self, a, b, graph, n):
        graph[a].remove(b)
        graph[b].remove(a)
        notSeen = set(range(n))
        
        # do the search
        q = deque()
        q.append(0)
        while(len(q)):
            current = q.popleft()
            if current in notSeen:
                notSeen.remove(current)
            else:
                continue
                
            for adjacent in graph[current]:
                if adjacent in notSeen:
                    q.append(adjacent)
        
        graph[a].add(b)
        graph[b].add(a)
        return len(notSeen) == 0