Posted on 2023-05-19 20:26
Uriel 阅读(20)
评论(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