886. Possible Bipartition - cocoder39/coco39_LC GitHub Wiki

886. Possible Bipartition

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
        
        color = {}
        for person, neighbors in graph.items():
            if person not in color:
                color[person] = 0
                queue = collections.deque([person])
                while queue:
                    sz = len(queue)
                    for i in range(sz):
                        cur_person = queue.pop()
                        next_color = 1- color[cur_person]
                        for neighbor in graph[cur_person]:
                            if neighbor not in color:
                                color[neighbor] = next_color
                                queue.append(neighbor)
                            elif color[neighbor] != next_color:
                                return False
        return True