木の直径
(Graph/Tree/diameter.py)

• View this file on GitHub
• Last update: 2021-01-11 01:21:49+09:00

概要

木の直径を求めるアルゴリズム。

使い方

diameter(tree: Sequence[Iterable[Tuple[int, int]]]) -> Tuple[int, List[int]]
隣接リストで表現された重み付き木 tree の直径とそのパスを返す。計算量 $O(V)$

Verified with

• TestCase/LibraryChecker/tree_diameter.test.py

Code

def diameter(tree):
    def _dfs(start):
        dist = [-1] * n
        dist[start] = 0
        stack = [start]
        while stack:
            v = stack.pop()
            for nxt_v, cost in tree[v]:
                if dist[nxt_v] != -1:
                    continue
                dist[nxt_v] = dist[v] + cost
                stack.append(nxt_v)
        max_d = max(dist)
        return dist.index(max_d), max_d, dist

    n = len(tree)
    u, _, _ = _dfs(0)
    v, diam, dist = _dfs(u)
    path = [v]
    while v != u:
        for nxt_v, cost in tree[v]:
            if cost + dist[nxt_v] == dist[v]:
                path.append(nxt_v)
                v = nxt_v
                break
    return diam, path

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