785. Is Graph Bipartite?

 

leetcode.com/problems/is-graph-bipartite/

Is Graph Bipartite? - LeetCode

주어진 그래프가 bipartite(이분 그래프)인지 판단하는 문제다.

큐를 이용해서 dfs를 구현하였다.

 

168 ms, faster than 81.64%

from collections import deque

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        EMPTY = -1
        BLUE = 0
        RED = 1
        
        color_dict = [EMPTY]*len(graph)
        
        Q = deque([])
        visited = set()
        for r, row in enumerate(graph):
            if r in visited:
                continue
            Q.append(r)
            color_dict[r] = BLUE
            
            while Q:
                cur_node = Q.popleft()
                if cur_node in visited:
                    continue
                
                for adj_node in graph[cur_node]:
                    if color_dict[adj_node] == EMPTY:
                        color_dict[adj_node] = RED if color_dict[cur_node] == BLUE else BLUE
                    else:
                        if color_dict[cur_node] == color_dict[adj_node]:
                            return False
                    Q.append(adj_node)
                    
                visited.add(cur_node)
        return True

156ms (랬는데 돌려보니 172ms)

from typing import List, Set


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if len(graph) == 1:
            return True
        colors = [None] * len(graph)

        def bfs(start: Set[int], color: int) -> bool:
            nextStarts: Set[int] = set()
            for node in start:
                colors[node] = 1 - color
                for neighbor in graph[node]:
                    if colors[neighbor] is None:
                        colors[neighbor] = color
                        nextStarts.add(neighbor)
                    elif colors[neighbor] != color:
                        return False
            if len(nextStarts) == 0:
                return True
            return bfs(nextStarts, 1 - color)

        while None in colors:
            if bfs({colors.index(None)}, 0) is False:
                return False
        return True