Posted on 2022-12-21 16:18
Uriel 閱讀(93)
評論(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