Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个无向图的边集,问是否是二分图,并查集基本应用

 1 #785
 2 #Runtime: 160 ms (Beats 23.18%)
 3 #Memory: 13.6 MB (Beats 95%)
 4 
 5 class Solution(object):
 6     def isBipartite(self, graph):
 7         """
 8         :type graph: List[List[int]]
 9         :rtype: bool
10         """
11         parent = [i for i in range(len(graph))]
12         
13         def find(x):
14             if parent[x] != x:
15                 parent[x] = find(parent[x])
16             return parent[x]
17         
18         def union(x, y):
19             fa, fb = find(x), find(y)
20             parent[fb] = fa
21         
22         for i in range(len(graph)):
23             for j in range(len(graph[i])):
24                 pi, pj = find(i), find(graph[i][j])
25                 if pi == pj:
26                     return False
27                 union(graph[i][0], graph[i][j])
28         
29         return True

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