Posted on 2023-06-04 23:18
Uriel 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code 、
并查集
求無向圖的聯通分支個數，DFS | BFS | 并查集 基本練習
DFS
1 #547
2 #Runtime: 154 ms (Beats 66.8%)
3 #Memory: 13.6 MB (Beats 94.53%)
4
5 class Solution(object):
6 def findCircleNum(self, isConnected):
7 """
8 :type isConnected: List[List[int]]
9 :rtype: int
10 """
11 ans = 0
12 n = len(isConnected)
13 vis = [0] * n
14
15 def DFS(node):
16 vis[node] = 1
17 for i in range(n):
18 if isConnected[node][i] == 1 and not vis[i]:
19 DFS(i)
20
21 for i in range(n):
22 if not vis[i]:
23 DFS(i)
24 ans += 1
25 return ans
BFS
1 #547
2 #Runtime: 156 ms (Beats 61.49%)
3 #Memory: 13.8 MB (Beats 40.4%)
4
5 class Solution(object):
6 def findCircleNum(self, isConnected):
7 """
8 :type isConnected: List[List[int]]
9 :rtype: int
10 """
11 ans = 0
12 n = len(isConnected)
13 vis = [0] * n
14 for i in range(n):
15 if not vis[i]:
16 q = deque([i])
17 vis[i] = 1
18 ans += 1
19 while q:
20 x = q.popleft()
21 for j in range(n):
22 if not vis[j] and isConnected[x][j]:
23 vis[j] = 1
24 q.append(j)
25 return ans
并查集
1 #547
2 #Runtime: 178 ms (Beats 21.88%)
3 #Memory: 13.5 MB (Beats 94.53%)
4
5 class Solution(object):
6 def findCircleNum(self, isConnected):
7 """
8 :type isConnected: List[List[int]]
9 :rtype: int
10 """
11 n = len(isConnected)
12 parent = [i for i in range(n)]
13
14 def find(x):
15 if parent[x] != x:
16 parent[x] = find(parent[x])
17 return parent[x]
18
19 def union(x, y):
20 fa, fb = find(x), find(y)
21 parent[fb] = fa
22
23 for i in range(n):
24 for j in range(n):
25 if isConnected[i][j]:
26 union(i, j)
27 return len(set([find(i) for i in range(n)]))