木の直径(diameter of a tree)

概要

木\(T\)の直径をなすパスの両端の頂点\(u, v\)とその長さ\(d\)を求める。

1回目のBFSで一方の頂点\(u\)を見つけ、2回目のBFSでもう一方の頂点\(v\)を見つける。

計算量

\(O(N)\)

実装

# N: 木Tの頂点数
# G[u] = [(w, c), ...]:
#   頂点uに隣接する頂点wとそれを繋ぐ辺の長さc

from collections import deque
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w, c in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + c
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

# パスu-vがこの木Tの直径(長さd)

Verified

  • AOJ: "GRL_5_A: Tree - Diameter of a Tree": source (Python3, 0.58sec)

  • AtCoder: "AtCoder Grand Contest 033 - C問題: Removing Coins": source (Python3, 814ms)