Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求无向图的联通分支个数,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)]))

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理