2색 색칠

def two_coloring(graph):
    color = [None] * len(graph)
    for source in range(len(graph)):
        if color[source] is not None:
            continue
        stack = [source]
        color[source] = True
        while stack:
            u = stack.pop()
            color_u = color[u]
            for v in graph[u]:
                if color[v] is None:
                    color[v] = not color_u
                    stack.append(v)
                elif color[v] == color_u:
                    raise ValueError('Not bipartite graph')
    return color

def two_coloring(graph: Graph) -> list[bool]:
    color = [None] * len(graph)
    for source in range(len(graph)):
        if color[source] is not None:
            continue
        color[source] = True
        queue = collections.deque([source])
        while queue:
            u = queue.popleft()
            col_u = color[u]
            for v in graph[u]:
                if color[v] is None:
                    color[v] = not col_u
                    queue.append(v)
                elif color[v] == col_u:
                    raise ValueError(
                        'Graph is not 2-colorable (not bipartite).'
                    )
    return color