1192. Critical Connections in a Network刷题笔记

参考这个题解，用的dfs

import collections
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        def makeGraph(coonections):
            graph = collections.defaultdict(list)
            for conn in connections:
                graph[conn[0]].append(conn[1])
                graph[conn[1]].append(conn[0])
            return graph
        
        graph = makeGraph(connections)
        connections = set(map(tuple,map(sorted,connections)))
        rank = [-2]*n
        
        def dfs(node, depth):
            if rank[node] >= 0:
                return rank[node]
            rank[node] = depth
            min_back_depth = n
            for neighbor in graph[node]:
                if rank[neighbor] == depth-1:
                    continue
                back_path = dfs(neighbor, depth+1)
                if back_path <= depth:
                    connections.discard(tuple(sorted((node,neighbor))))
                min_back_depth = min(min_back_depth,back_path)
            rank[node] = n
            return min_back_depth
        dfs(0,0)
        return list(connections)