• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

木の直径

date: 2021-04-20 excerpt: 木の直径について

tag: algorithmgraphdp


木の直径について

概要

  • グラフで最も距離が離れた2つの点の距離を木の直径という

求め方

  • 任意のスタートの頂点から最も遠い点(S)を調べる(dfs, bfs)
    1. 任意の点から最も遠い点を\(S\)をdfs/bfsで求める
    2. \(S\)から最も遠い点\(Sd\)をdfs/bfsで求める
    3. \(S\)から\(Sd\)の距離が木の直径である
  • つまり二回dfs/bfsで計算する必要がある

参考

  • 木の直径を求めるアルゴリズム@algo-logic

例; 最長距離を求める問題=木の直径を求める問題

問題

  • AtCoder Beginner Contest 151; D - Maze Master

解説

  • 再長距離=木の直径と考える
  • ワーシャルフロイド法でも解けるが木の直径でも解ける

解答

import collections

H, W = map(int,input().split())
S = [list(input()) for h in range(H)]
G = collections.defaultdict(set)

for h in range(H):
    for w in range(W):
        ss = S[h][w]
        if ss == "#":
            continue
        for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nh, nw = h+dh, w+dw
            if not(0 <= nh < H and 0<= nw < W):
                continue
            if S[nh][nw] == "#":
                continue
            G[(h,w)].add( (nh, nw) )
            G[(nh,nw)].add( (h, w) )

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            start = (h, w)
            break


que = collections.deque([(start, 0)])
max_pos = (0, (-1, -1))
vis = set()
while que:
    i, cnt = que.popleft()
    if i in vis:
        continue
    max_pos = max(max_pos, (cnt, i))
    vis.add(i)
    for j in G[i]:
        if j in vis:
            continue
        que.append((j, cnt+1))
_, start = max_pos

que = collections.deque([(start, 0)])
max_pos = (0, (-1, -1))
vis = set()
while que:
    i, cnt = que.popleft()
    if i in vis:
        continue
    max_pos = max(max_pos, (cnt, i))
    vis.add(i)
    for j in G[i]:
        if j in vis:
            continue
        que.append((j, cnt+1))
ans, _ = max_pos

print(ans)


algorithmgraphdp Share Tweet