Существует n
серверов, пронумерованных от 0
до n - 1
, соединенных ненаправленными связями между серверами
, образующими сеть, где 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]]