Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一些id pairs,[a, b]表示a不想与b分在一组,一共n个id,问是否可以分成两个group。
并查集,对于每个id i,预处理所有不能和他一组的ids,这些ids将会被分在一组(并查集union操作),如果发现i和这些id在并查集的同一组,则输出False


 1 #886
 2 #Runtime: 2223 ms (Beats 5.11%)
 3 #Memory: 19.1 MB (Beats 72.26%)
 4 
 5 class UnionFind:
 6     def __init__(self, n):
 7         self.parent = [i for i in range(n + 1)]
 8     def find(self, x):
 9         i = x
10         while self.parent[x] != x:
11             x = self.parent[x]
12         self.parent[i] = x
13         return x
14     def union(self, x, y):
15         self.parent[self.find(x)] = self.find(y)
16 
17 
18 class Solution(object):
19     def possibleBipartition(self, n, dislikes):
20         """
21         :type n: int
22         :type dislikes: List[List[int]]
23         :rtype: bool
24         """
25         if n == 1:
26             return True
27         graph_dict = {}
28         for d in dislikes:
29             if d[0] not in graph_dict:
30                 graph_dict[d[0]] = [d[1]]
31             else:
32                 graph_dict[d[0]].append(d[1])
33             if d[1] not in graph_dict:
34                 graph_dict[d[1]] = [d[0]]
35             else:
36                 graph_dict[d[1]].append(d[0])
37         uf_set = UnionFind(n)
38         for x in graph_dict.keys():
39             for i in range(len(graph_dict[x]) - 1):
40                 uf_set.union(graph_dict[x][i], graph_dict[x][i + 1])
41             if uf_set.find(x) == uf_set.find(graph_dict[x][0]):
42                 return False
43         return True

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