染色法
有个卡点就是这个图不一定是整个连通的。
from collections import deque class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: visited = [False]*len(graph) color = [True]*len(graph) queue = deque() while True: if not queue: for i in range(len(graph)): if visited[i] or len(graph[i])==0: continue queue.append(i) visited[i]=True color[i]=True break if not queue: break tmp = queue.popleft() for i in graph[tmp]: if visited[i]: if color[i] == (not color[tmp]): continue else: return False else: visited[i] = True color[i] = not color[tmp] queue.append(i) return True