LC785.判断二分图 LeetCode 785
方法一: BFS + 染色
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# BFS
from collections import deque
n = len(graph)
UNCOLORED, RED, GREEN = 0, 1, 2
color = [UNCOLORED]*n # 暂时标记为颜色0
# 颜色: 0 代表未被涂色
q = deque()
q.append(0)
color[0] = RED
round_cnt = 0
for i in range(n):
if color[i] == UNCOLORED:
q.append(i)
while q:
round_cnt +=1
for _ in range(len(q)):
cur_node = q.popleft()
color_next = GREEN if color[cur_node] == RED else RED
for next_i in graph[cur_node]:
if color[next_i] == UNCOLORED:
color[next_i] = color_next
q.append(next_i)
elif color[next_i] != color_next:
return False
return True
方法二: DFS + 染色
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# DFS
n = len(graph)
UNCOLORED, RED, GREEN = 0, 1, 2
color = [UNCOLORED]*n # 暂时标记为颜色0
# 颜色: 0 代表未被涂色
res = True
def dfs(x, color_cur):
nonlocal res
color[x] = color_cur
color_next = GREEN if color[x] == RED else RED
for next_i in graph[x]:
if color[next_i] == UNCOLORED:
color[next_i] = color_next
dfs(next_i, color_next)
if res == False:
return
elif color[next_i]!=color_next:
res = False
return
#return True
for i in range(n):
if color[i] == UNCOLORED:
dfs(i, RED)
if res == False:
break
return res
方法三:并查集
class UnionFind:
def __init__(self, n):
self.root = [i for i in range(n)]
self.rank = [1]*n
self.cnt = n
def find(self, x):
if x == self.root[x]:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x]>self.rank[root_y]:
self.root[root_y] = root_x
elif self.rank[root_y] >self.rank[root_x]:
self.root[root_x] = root_y
else:
self.root[root_y] = root_x
self.rank[root_x]+=1
def isConnected(self, x, y):
return self.find(x) == self.find(y)
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# 并查集
n = len(graph)
uf = UnionFind(n)
for i in range(n):
for next_i in graph[i]:
if uf.isConnected(i, next_i):
return False
uf.union(graph[i][0], next_i) # 注意这里用的是和next_i “同组”的第一个节点,不能用i, 即uf.union(i, next_i)是错误的
return True