is_bipartite_graph¶
ソースコード¶
from titan_pylib.graph.is_bipartite_graph import is_bipartite_graph
展開済みコード¶
1# from titan_pylib.graph.is_bipartite_graph import is_bipartite_graph
2def is_bipartite_graph(G: list[list[int]]) -> bool:
3 col = [-1] * len(G)
4 for i in range(len(G)):
5 if col[i] != -1:
6 continue
7 col[i] = 0
8 stack = [i]
9 while stack:
10 v = stack.pop()
11 cx = 1 - col[v]
12 for x in G[v]:
13 if col[x] == -1:
14 col[x] = cx
15 stack.append(x)
16 elif col[x] != cx:
17 return False
18 return False if -1 in col else True