トポロジカルソート (Kahn のアルゴリズム)
(Graph/misc/topological_sorted.py)

• View this file on GitHub
• Last update: 2021-01-15 02:43:02+09:00

概要

有向グラフに対してトポロジカルソートをする。グラフが巡回するときは未定義。

使い方

topological_sorted(digraph: Sequence[Sequence[int]]) -> Tuple[bool, List[int]]
有向グラフに対してトポロジカルソートを行い、非巡回判定 ( True : 非巡回、False : 巡回あり) とトポロジカル順の配列を返す。判定が False の場合、トポロジカル順は未定義。計算量 $O(V + E)$

Verified with

• TestCase/AOJ/GRL_4_B.test.py

Code

def topological_sorted(digraph):
    n = len(digraph)
    indegree = [0] * n
    for v in range(n):
        for nxt_v in digraph[v]:
            indegree[nxt_v] += 1

    tp_order = [i for i in range(n) if indegree[i] == 0]
    stack = tp_order[:]
    while stack:
        v = stack.pop()
        for nxt_v in digraph[v]:
            indegree[nxt_v] -= 1
            if indegree[nxt_v] == 0:
                stack.append(nxt_v)
                tp_order.append(nxt_v)

    return len(tp_order) == n, tp_order

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