AOJ: Library of Graph Algorithms

GRL_5_A(bfs).py

# AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2434976#1)
# BFS二回で求める解法: 計算量 O(N)
from collections import deque
n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    s, t, w = map(int, raw_input().split())
    G[s].append((t, w))
    G[t].append((s, w))
 
# queue を collections.deque で行う
deq = deque()
def bfs(s):
    used = {s: 0} # (key: 頂点, value: 点sからの距離)
    deq.append(s)
    while deq:
        s = deq.popleft()
        for t, w in G[s]:
            if t in used:
                continue
            used[t] = used[s] + w
            deq.append(t)
    # (<頂点sから最遠となる頂点>, <最遠となる時の距離>) を返すように計算
    return used.items()[used.values().index(max(used.values()))]
t, co = bfs(0)
print bfs(t)[1]

GRL_5_A(dfs).py

# RE (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2434937#1)
# DFS二回で求める解法: 計算量 O(N)
# 弱いケースは枝分かれしない木
# => スタックフレーム用のメモリ不足で死ぬ ("Segmentation fault: 11")
import sys
sys.setrecursionlimit(10**6)
n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    s, t, w = map(int, raw_input().split())
    G[s].append((t, w))
    G[t].append((s, w))

# (<頂点sからの最遠の距離>, <最遠となる頂点>) を返すDFS
def dfs(s, prev):
    if prev != -1 and len(G[s]) == 1:
        return (0, s)
    res = (0, s)
    for t, w in G[s]:
        if t == prev:
            continue
        cost, v = dfs(t, s)
        # コストが大きい方を答えとして残す
        res = max(res, (cost + w, v))
    return res
co, t = dfs(0, -1)
print dfs(t, -1)[0]

GRL_5_B.py

# AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2435014#1)
# 各頂点からの木の高さは、直径となす２つの頂点u, vとの距離のうち最大のものとなる
# 計算量 O(N)
from collections import deque
n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    s, t, w = map(int, raw_input().split())
    G[s].append((t, w))
    G[t].append((s, w))
 
deq = deque()
def max_dist(dist):
    return dist.items()[dist.values().index(max(dist.values()))]

def bfs(s):
    dist = {s: 0}
    deq.append(s)
    while deq:
        s = deq.popleft()
        for t, w in G[s]:
            if t in dist:
                continue
            dist[t] = dist[s] + w
            deq.append(t)
    return dist

# 直径をなす２つの頂点を求める
u, co = max_dist(bfs(0))
v, co = max_dist(bfs(u))

# ２つの頂点と各頂点との距離を計算
dist1 = bfs(u); dist2 = bfs(v)
for i in xrange(n):
    print max(dist1[i], dist2[i])

GRL_5_C.py

# AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2435099#1)
# LCAを二分探索で計算: 計算量 O((N + Q)logN)
# 二分探索するために以下を求める
#      depth[i]: 頂点iの深さ
#  parent[i][k]: 頂点iから2**k個親頂点に戻った時の頂点
from collections import deque
n = input()
 
C = [None]*n # C[i]: 頂点iの子頂点リスト
P = [None]*n # P[i]: 頂点iの親頂点
for i in xrange(n):
    ipt = map(int, raw_input().split())
    C[i] = ipt[1:]
    for c in C[i]:
        P[c] = i

# LEV = logN程度
LEV = (n+1).bit_length()

# 親頂点計算
# parent[i][k+1] = parent[ parent[i][k] ][k] という関係から計算していく
# Noneは頂点が存在しない場合
parent = [[None]*(LEV + 1) for i in xrange(n)]
for i in xrange(n):
    parent[i][0] = P[i]
for k in xrange(LEV):
    for i in xrange(n):
        if parent[i][k] is None:
            parent[i][k+1] = None
        else:
            parent[i][k+1] = parent[parent[i][k]][k]
# 深さ計算
depth = [None]*n
deq = deque()
deq.append(0)
depth[0] = 0
while deq:
    v = deq.popleft()
    for c in C[v]:
        deq.append(c)
        depth[c] = depth[v] + 1

# クエリ処理
q = input()
for t in xrange(q):
    u, v = map(int, raw_input().split())
    if not depth[u] < depth[v]:
        u, v = v, u
    # u, v から同じ深さの頂点に移動
    for k in xrange(LEV+1):
        if ((depth[v] - depth[u]) >> k) & 1:
            v = parent[v][k]
    # 同じ深さでLCAの場合
    if u == v:
        print u
        continue
 
    # u, vから2**k個親頂点に移動して異なれば移動、そうでなければ移動しない
    # これをk = LEV, LEV-1, ..., 1, 0 に対して行う
    for k in xrange(LEV, -1, -1):
        if parent[u][k] != parent[v][k]:
            u = parent[u][k]
            v = parent[v][k]
    # １つ戻すとLCAになる
    print parent[u][0]