Neterukun's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Neterukun1993/Library

:heavy_check_mark: 二部グラフ判定 (DFS)
(Graph/misc/is_bipartite.py)

Verified with

Code

def is_bipartite(graph):
    n = len(graph)
    cols = [-1] * n
    cnts = []
    for v in range(n):
        if cols[v] != -1:
            continue
        cols[v] = 0
        cnt = [1, 0]
        stack = [v]
        while stack:
            v = stack.pop()
            for nxt_v in graph[v]:
                if cols[nxt_v] != -1:
                    if cols[nxt_v] == cols[v] ^ 1:
                        continue
                    else:
                        return False, cols, cnts
                cols[nxt_v] = cols[v] ^ 1
                cnt[cols[nxt_v]] += 1
                stack.append(nxt_v)
        cnts.append(cnt)
    return True, cols, cnts
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError
Back to top page