木の重心
(Graph/Tree/centroid.py)

• View this file on GitHub
• Last update: 2021-02-16 00:44:23+09:00

概要

木の重心を求めるアルゴリズム。重心は最大で 2 つ存在する。木の代わりに森を与えた場合はバグるので注意。

使い方

centroid(tree: Sequence[Iterable[int]]) -> List[int]
隣接リストで表現された木 tree の重心を格納した配列を返す。計算量 $O(V)$

Depends on

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

Required by

• 木のハッシュ (木の同型判定) (Graph/Tree/treehash.py)

Verified with

• TestCase/AOJ/2821.test.py

Code

from Graph.Tree.topological_sorted import topological_sorted


def centroid(tree):
    n = len(tree)
    tp_order, par = topological_sorted(tree)
    sub_size = [0] * n
    res = []
    for v in tp_order[::-1]:
        is_centroid = True
        sub_size[v] = 1
        for nxt_v in tree[v]:
            if nxt_v == par[v]:
                continue
            if sub_size[nxt_v] > n // 2:
                is_centroid = False
            sub_size[v] += sub_size[nxt_v]
        if is_centroid and n - sub_size[v] <= n // 2:
            res.append(v)
    return res

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