可能的二分法 -- 二分图判定【DFS、BFS分别实现】

886. 可能的二分法

class PossibleBipartition:"""可能的二分法「其实考察的就是二分图的判定」用dfs和bfs 两种方法分别实现https://leetcode.cn/problems/possible-bipartition/"""def __init__(self):self.success = Trueself.color = []self.visited = []def dfs(self, n, dislikes):"""DFS递归实现:param n: :param dislikes::return:"""# 图节点编号为 1...nself.color = [False] * (n+1)self.visited = [False] * (n+1)graph = self.buildgraph(n, dislikes)# 因为图不一定是联通的，可能存在多个子图# 所以要把每个节点都作为起点进行一次遍历# 如果发现任何一个子图不是二分图，整幅图都不是二分图for v in range(1, n+1):if not self.visited[v]:self.dfs_traverse(graph, v)return self.successdef buildgraph(self, n, dislikes):graph = [[] for _ in range(n+1)]for edge in dislikes:v = edge[1]w = edge[0]# 无向图相当于双向图graph[v].append(w)graph[w].append(v)return graphdef dfs_traverse(self, graph, v):if not self.success:returnself.visited[v] = Truefor w in graph[v]:if not self.visited[w]:self.color[w] = not self.color[v]self.dfs_traverse(graph, w)else:if self.color[v] == self.color[w]:self.success = Falsereturndef bfs(self, n, dislikes):"""BFS实现，用队列替代递归调用:param n::param dislikes::return:"""# 图节点编号为 1...nself.color = [False] * (n + 1)self.visited = [False] * (n + 1)graph = self.buildgraph(n, dislikes)# 因为图不一定是联通的，可能存在多个子图# 所以要把每个节点都作为起点进行一次遍历# 如果发现任何一个子图不是二分图，整幅图都不是二分图for v in range(1, n + 1):if not self.visited[v]:self.bfs_traverse(graph, v)return self.successdef bfs_traverse(self, graph, start):# 节点队列queue = []self.visited[start] = Truequeue.append(start)while queue and self.success:v = queue.pop(0)# 从节点 v 向所有相邻节点扩散for w in graph[v]:if not self.visited[w]:# 相邻节点w没有被访问过# 那么应该给节点w涂上和节点v不同的颜⾊self.color[w] = not self.color[v]# 标记 w 节点，并放⼊队列self.visited[w] = Truequeue.append(w)else:if self.color[v] == self.color[w]:self.success = Falsereturn