Posted on 2023-05-19 20:26
Uriel 閱讀(53)
評論(0) 編輯 收藏 引用 所屬分類:
圖論 、
閑來無事重切Leet Code 、
并查集
給出一個無向圖的邊集，問是否是二分圖，并查集基本應用
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