競プロ典型90問：003 - Longest Circular Road（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_c

挑戦結果

• 解けなかった

考えたこと

• ワーシャルフロイドで全ノード間の距離を求めて、その最長の距離に+1すれば良いと思った。
• コード書いたけどTLEした。$N³$では無理だった。
• グラフの直径を求めれば良いことがわかった。ググったところアルゴリズムは理解した。
• ただ、上手に実装できなくてTLEした。

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

1. 任意の頂点から最長の頂点uを探索
2. 頂点uから最長の頂点vを探索
3. uとvを結ぶパスが最長

解説を読んだふりかえり

• グラフをマトリックスで持ったことで計算量が上がっているようだった。

ソース

from collections import deque
N = int(input())
INF = float('inf')
# グラフ
G = [[] * (N+1) for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    G[a].append(b)
    G[b].append(a)
# stからの距離を配列で返す
def getdist(st):
    visited = {st}
    dist = [INF] * (N+1)
    dist[st] = 0
    Q = deque([st])
    while len(Q)>0:
        node = Q.popleft()
        for nextnode in G[node]:
            if nextnode in visited:
                continue
            dist[nextnode] = min(dist[nextnode], dist[node]+1)
            visited.add(nextnode)
            Q.append(nextnode)
    return dist

## グラフの直径を求める 
# 任意の場所stから各ノードへの最短距離を求める
st1 = 1
dist1 = getdist(st1)
# stからの距離が最大なノード(idx)を求める
d = idx = 0
for i in range(2,N+1):
    if d<dist1[i]:
        d=dist1[i]
        idx = i
# idxから各ノードへの最短距離を求める
dist2 = getdist(idx)
# 各最短距離の中で、最大の値がグラフの直径。 今回の問題は直径+1が答え。
print(max(dist2[1:]) + 1)