[Python手撕]判断二分图
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
def bfs(i):
color[i] = 1
queue = [(i,1)]
while queue:
t,c = queue.pop(0)
nc = 0
if c == 1:
nc = -1
else:
nc = 1
for nt in graph[t]:
if color[nt] != 0 and color[nt] == c:
return False
elif color[nt] == 0:
color[nt] = nc
queue.append((nt,nc))
return True
n = len(graph)
color = [0] * n
for i in range(n):
if color[i] == 0:
if not bfs(i):
return False
return True