題目在此 1192. Critical Connections in a Network
![image 13]()
給一個 graph 請找出所有 critical connections
解題思維
這題就是要你各位重新複習一下 Tarjan’s algorithm
基本概念就是找出環出來，如果不是環的一部分那就是 critical connections
那我推薦下面這個 Youtube 影片，解說得很清楚明白
如果是要計算點，可以參考 Articulation Points
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
graph = collections.defaultdict(set)
for u, v in connections:
graph[u].add(v)
graph[v].add(u)
steps = [-1] * n
result = []
def dfs(parent_node, cur_node, cur_step):
steps[cur_node] = cur_step
for next_node in graph[cur_node]:
if next_node == parent_node:
continue
if steps[next_node] == -1:
steps[next_node] = dfs(cur_node, next_node, cur_step + 1)
steps[cur_node] = min(steps[cur_node], steps[next_node])
if steps[next_node] == cur_step + 1:
result.append([cur_node, next_node])
return steps[cur_node]
dfs(-1, 0, 0)
return result
|
也許你也會想看看
