涉及到的题目：
886. 可能的二分法
785. 判断二分图
https://blog.csdn.net/qq_21201267/article/details/105294270
此类题目的关键在于构建图，然后将一条边上两个点着不同的颜色，当着色方案为2种颜色时，即为所说的二分图问题。
886. 可能的二分法
class Solution: def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool: color = {} graph = collections.defaultdict(set) for i,j in dislikes: graph[i].add(j) graph[j].add(i) def dfs(i): nei = graph[i] for j in nei: if j not in color: color[j] = color[i] ^ 1 if not dfs(j): return False elif color[j] == color[i]: return False return True for i in range(1,N+1): if i not in color: color[i] = 0 if not dfs(i): return False return True 785. 判断二分图
DFS版本：
class Solution(object): def isBipartite(self, graph): “”” :type graph: List[List[int]] :rtype: bool “”” n = len(graph) visited = [-1] * n for i in range(n): if visited[i] == -1: if not self.dfs(graph, i, 0, visited): return False return True def dfs(self, graph, v, color, visited): visited[v] = color for i in graph[v]: if visited[i] == -1: if not self.dfs(graph, i, 1 – color, visited): return False elif visited[i] == color: return False return True
BFS版本：
class Solution(object): def isBipartite(self, graph): n = len(graph) visited = [-1] * n for i in range(n): if visited[i] == -1: if not self.bfs(graph, i, 0, visited): return False return True def bfs(self, graph, v, color, visited): visited[v], queue = color, [v] while queue: node = queue.pop(0) for i in graph[node]: if visited[i] == -1: visited[i] = 1 – visited[node] queue.append(i) elif visited[i] == visited[node]: return False return True
