Is Graph Bipartite?

Intuition

A graph is bipartite exactly when it has no odd-length cycle. We can test this by coloring: pick a start node, color it, and give every neighbor the opposite color. Continuing this outward, each edge must connect two differently colored nodes. If we ever reach a node that already carries the same color as the node we came from, an odd cycle exists and the graph cannot be split in two. Because the graph may be disconnected, we launch a fresh traversal from every still-uncolored node.

Algorithm walkthrough

1. 1Create a color array of length n filled with 0 (meaning uncolored); we will use +1 and -1 for the two sets.
2. 2Loop over every node; skip any node that already has a color from a previous traversal.
3. 3Color the start node +1 and push it into a queue to begin a BFS over its component.
4. 4Pop a node, and for each neighbor: if uncolored, assign it the negated color of the current node and enqueue it.
5. 5If a neighbor already shares the current node's color, return false immediately - an edge lies inside one set.
6. 6If all components are colored without conflict, return true.

Implementation

from collections import deque
from typing import List

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