Posted on 2022-12-21 16:18
Uriel 阅读(43)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
闲来无事重切Leet Code 、
并查集
给出一些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