[LeetCode] 886. Possible Bipartition

- Problem

886. Possible Bipartition

- 내 풀이

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True

        def bfs(x):
            q = collections.deque([x])

            while q:
                cur = q.popleft()
                cur_color = color[cur]
                for nei in graph[cur]:
                    if color[nei] == cur_color:
                        return False
                    elif color[nei] == 0:
                        color[nei] = -cur_color
                        q.append(nei)
            return True
        
        graph = [[] for _ in range(n+1)]
        color = [0] * (n+1)
        
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)

        for i in range(1, n+1):
            if not color[i]:
                color[i] = 1
                result = bfs(i)
                if result == False:
                    return False
        
        return True

- 결과