本文共 1144 字，大约阅读时间需要 3 分钟。

题目：（中等）

标签：图、深度优先搜索、广度优先搜索

解法一：

def build_graph(edges):    graph = collections.defaultdict(set)    for edge in edges:        graph[edge[0]].add(edge[1])        graph[edge[1]].add(edge[0])    return graphclass Solution:    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:        graph = build_graph(dislikes)        table = [0] * (N + 1)        for m1, m2 in dislikes:            if table[m1] * table[m2] > 0:                return False            if table[m1] != 0 or table[m2] != 0:                continue            table[m1] = 1            now = -1            queue = collections.deque([m1])            while queue:                for _ in range(len(queue)):                    n1 = queue.popleft()                    for n2 in graph[n1]:                        if table[n2] == -now:                            return False                        elif table[n2] == 0:                            table[n2] = now                            queue.append(n2)                now *= -1        return True

转载地址：https://dataartist.blog.csdn.net/article/details/112787697 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！