LeetCode 筆記 - 1192. Critical Connections in a Network

Posted on

題目在此 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
35
36
37
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        
        # init
        jump = [-1] *n
        
        graph = {}
        for s0, s1 in connections:
            if s0 not in graph:
                graph[s0] = set()
            graph[s0].add(s1)
            
            if s1 not in graph:
                graph[s1] = set()
            graph[s1].add(s0)
            
        result = []
        
        # define dfs
        def dfs(parent_index:int, current_index: int, step:int) -> int:
            jump[current_index] = step + 1
            for child in graph[current_index]:
                if child == parent_index:
                    continue
                if jump[child] == -1:
                    jump[current_index] = min(jump[current_index], dfs(current_index, child, step + 1))
                else:
                    jump[current_index] = min(jump[current_index], jump[child])
                    
            if jump[current_index] == step + 1 and current_index != 0:
                result.append([parent_index, current_index])
            
            return jump[current_index]
        
        dfs(-1, 0, 0)
        
        return result

相關文章