Source code for titan_pylib.graph.is_bipartite_graph


[docs]
 1def is_bipartite_graph(G: list[list[int]]) -> bool:
 2    col = [-1] * len(G)
 3    for i in range(len(G)):
 4        if col[i] != -1:
 5            continue
 6        col[i] = 0
 7        stack = [i]
 8        while stack:
 9            v = stack.pop()
10            cx = 1 - col[v]
11            for x in G[v]:
12                if col[x] == -1:
13                    col[x] = cx
14                    stack.append(x)
15                elif col[x] != cx:
16                    return False
17    return False if -1 in col else True