785. Is Graph Bipartite? - cocoder39/coco39_LC GitHub Wiki

785. Is Graph Bipartite?

Color the graph by bfs/dfs

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = {}
        for node in range(len(graph)):
            if node in color:
                continue
            color[node] = 0
            
            queue = collections.deque()
            queue.append(node)
            while queue:
                cur_node = queue.popleft()
                next_col = 1 if color[cur_node] == 0 else 0
                for neighbor in graph[cur_node]:
                    if neighbor not in color:
                        color[neighbor] = next_col
                        queue.append(neighbor)
                    elif color[neighbor] != next_col:
                        return False
        return True

Time complexity is O(V+E) where V is #nodes (ie, len(graph)) and E is #edges