概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題003-Longest Circular Road
問題概要
グラフの中で最も経路が長くなる都市の組み合わせを探し、＋１して出力する。
制約
3 <= N <= 100000 \\
1 <= Ai < Bi <= N \\
(1 <= i <= N-1) \\
・どの都市間も移動ができ、入力は全て整数。
解き方
まず初めに、
グラフの中で最も経路が長くなる都市の組み合わせを探し、
どうして上記のように定められるかというと、例えば以下の画像を例に見てみると直感的に８と９を線で繋ぐのが良いと分かるかと思います。
ここで、１からの距離が最も遠いもの同士を繋ぐという考え方も出来ますが、
この考えでは、9と10のように近いものも候補に上がり、最悪の場合、N通りもあり得るため、全て調べるのは現実的ではありません。
また、(沼にハマっている方は)経路を足すことによって、最大の経路が変わるのでは？と考えられているかもしれませんが、これは
- 道路がN-1本
- どの都市間も移動可能
という条件があるため、今回の場合は無視できます。
では、最大の経路となる組み合わせの求め方ですが、これはある１点から、最も距離のある点を導き、その点からさらに最も距離のある点を調べることで求められます。
（上記の画像では、１から最も深い点８を求め、８から再度探索をすることで求められます。）
探索の方法は、道路に重みなどもないため、幅優先探索で良いかと思います。
（幅優先探索については、こちらをご参考ください。）
実装の流れは以下になります。
- 都市１から幅優先探索を用いて、最も離れている都市を見つける。
- １で求めた都市から幅優先探索を用いて、最長となる経路を求める。
幅優先探索の計算量は、頂点数＋辺の数なので、今回の場合は、$N+N-1$、
これを２回行うため、合計で$4N$、すなわち$O(N)$。これは、10^5のオーダーになるので、十分に間に合います。
引用元：競プロ典型90問 Github
実装
# キューのインポート
from collections import deque
# 入力の受け取り、道路情報はリストで格納
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
A, B = map(int, input().split())
G[A-1].append(B-1)
G[B-1].append(A-1)
# 幅優先探索をする関数。今回は１回目の探索で都市が、２回目の探索で長さが必要なため、arrで値を管理した。
def bfs(n):
Q = deque()
dist = [-1]*N
dist[n] = 0
Q.append(n)
arr = [0, 0]
while Q:
i = Q.popleft()
for j in G[i]:
if dist[j] == -1:
a = dist[i]+1
dist[j] = a
Q.append(j)
if a > arr[1]:
arr = [j, a]
return arr
# １回目は０から呼び出し、２回目はbfsからの返り値で呼び出す。
p, dep = bfs(0)
p2, dep2 = bfs(p)
print(dep2+1)
最後に
今回の問題は、
- 木の中で最長となる経路は２回の探索で求められる
- 幅優先探索の実装方法
の２点が大きなポイントでした。
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）
ここまでお読みいただきありがとうございました。