木上のトポロジカルソート
(Graph/Tree/topological_sorted.py)

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

概要

木 (もしくは森) に対してトポロジカルソートをする。木 DP を非再帰で行いたいときに使用する。

使い方

topological_sorted(tree: Sequence[Iterable[int]], root: Optional[int] = None) -> Tuple[List[int], List[int]]
木（もしくは森）に対してトポロジカルソートを行い、トポロジカル順の配列と親頂点の配列を返す。根頂点 root を指定しない場合は、未訪問の頂点すべてに対してトポロジカルソートを行う。計算量 $O(V)$

Required by

• 木の重心 (Graph/Tree/centroid.py)
• DSU on tree (Graph/Tree/dsu_on_tree.py)
• 木のハッシュ (木の同型判定) (Graph/Tree/treehash.py)

Verified with

• TestCase/yukicoder/yuki0763.test.py

Code

def topological_sorted(tree, root=None):
    n = len(tree)
    par = [-1] * n
    tp_order = []
    for v in range(n):
        if par[v] != -1 or (root is not None and v != root):
            continue
        stack = [v]
        while stack:
            v = stack.pop()
            tp_order.append(v)
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                par[nxt_v] = v
                stack.append(nxt_v)
    return tp_order, par

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