algorithm_library/python/graph/BipartiteGraph.py

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00

Code

from collections import defaultdict,deque

# 二部グラフなら True と色分けを返す
def is_bipartite_graph(G : list[list[int]], N : int) -> tuple[bool, list[int]]:
  col = [-1]*(N+1)
  def dfs(v):
    que = deque()
    que.append(v)
    while que:
      v = que.pop()
      for v2 in G[v]:
        if col[v2]!=-1:
          if col[v]==col[v2]:
            return False
          continue
        col[v2] = 1-col[v]
        que.append(v2)
    return True

  for v in range(1,N+1):
    if col[v]!=-1: continue
    col[v] = 1
    if dfs(v) == False:
      return False, []
  
  return True, col

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.0/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.0/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page