네트워크의 중요한 연결

n에서 0까지 번호가 매겨진 n - 1 서버가 무방향 서버 대 서버connections로 연결되어 네트워크를 형성하며 여기서 connections[i] = [ai, bi]는 서버ai와 bi 사이의 연결을 나타냅니다. 모든 서버는 네트워크를 통해 직접 또는 간접적으로 다른 서버에 도달할 수 있습니다.

중요한 연결은 제거될 경우 일부 서버가 다른 서버에 연결할 수 없게 만드는 연결입니다.

순서에 관계없이 네트워크의 모든 중요한 연결을 반환합니다.

예 1:



입력: n = 4, 연결 = [[0,1],[1,2],[2,0],[1,3]]
출력: [[1,3]]
설명: [[3,1]]도 허용됩니다.

예 2:

입력: n = 2, 연결 = [[0,1]]
출력: [[0,1]]

제약:

2 <= n <= 105

n - 1 <= connections.length <= 105

0 <= ai, bi <= n - 1

ai != bi

반복되는 연결이 없습니다.

해결책:

from collections import defaultdict

class Solution:
    def DFS(self, graph, node, v, parent, disc, low):
        v.add(node)
        disc[node] = self.t
        low[node] = self.t
        self.t += 1
        for j in graph[node]:
            if j not in v:
                parent[j] = node
                self.DFS(graph, j, v, parent, disc, low)
                low[node] = min(low[node], low[j])
            elif j != parent[node]:
                low[node] = min(low[node], disc[j])

    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        for a, b in connections:
            graph[a].append(b)
            graph[b].append(a)
        self.t = 0
        parent = defaultdict(lambda: -1)
        disc = defaultdict(lambda: float('inf'))
        low = defaultdict(lambda: float('inf'))
        v = set()
        for i in range(n):
            if i not in v:
                self.DFS(graph, i, v, parent, disc, low)
        return [[u, v] for u, v in connections if low[u] > disc[v] or low[v] > disc[u]]