そまちょブログのそまちょ(@somachob)です。
この記事は、AtCoder Beginner Contest 309 の D問題についての解説です。
D – Add One Edge
入力例1をもとに解説します。
見出し
3 4 6
1 2
2 3
4 5
4 6
1 3
6 7
入力を受け取ります。
グラフの問題なので、グラフで受け取ってます。
管理しやすいように、頂点は ‐1 で受け取ります。
頂点1は0、頂点2は1、頂点3は2、…というようになります。
# 入力
N1, N2, M = map(int, input().split())
graph = [[] for _ in range(N1 + N2)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
# 入力確認
print(N1, N2, M)
print(graph)
""" 出力結果
3 4 6
[[1, 2], [0, 2], [1, 0], [4, 5], [3], [3, 6], [5]]
"""
入力の受け取りについて、わからない場合は次の記事を参考にしてください。
幅優先探索
この問題は、次の2つの距離を足したものに1を足したものを解答すればいいことになります。
- 頂点1からの最大距離
- 頂点N1+N2からの最大距離
これがわかれば、頂点1からの幅優先探索と頂点N1+N2からの幅優先探索をしてその最大値に1を足せばいいです。
幅優先探索について、解説した記事も参考にしてください。
基本的な幅優先探索は、次のようなコードになります。
0から幅優先探索をして0からの距離を distance に格納します。
from collections import deque
# 入力
N, M = map(int, input().split)
graph= [[] for _ in range(M)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
# 変数の初期化
queue = deque()
distance = [-1] * N
# 頂点0 から探索
queue.append(0)
distance[0] = 0
while queue:
# 探索する頂点の取得
v =queue.popleft()
# 探索する頂点からつながっている頂点への探索
for next_v in graph[v]:
# 探索済みのとき
if distance[next_v] != -1:
continue
# 次の頂点を追加
queue.append(next_v)
distance[next_v] = distance[v] + 1
これをもとに頂点1と頂点N1+N2からの最大距離を足したものに1を足したものが答えになります。
これを実装したものが次のコードになります。
幅優先探索を関数にして、その最大の距離を返す関数を実装して、頂点1と頂点N1+N2からの最大距離を取得しています。
実装の関係上、頂点番号は実際の頂点-1になっていることに注意してください。
from collections import deque
# 入力
N1, N2, M = map(int, input().split())
graph= [[] for _ in range(N1 + N2)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
# 幅優先探索の関数
def bfs(u):
# 変数の初期化
queue = deque()
distance = [-1] * (N1 + N2)
# 頂点 u から幅優先探索
queue.append(u)
distance[u] = 0
# 幅優先探索
while queue:
# 探索する頂点の取得
v = queue.popleft()
# 探索する頂点からつながっている頂点への探索
for next_v in graph[v]:
# 探索済みのとき
if distance[next_v] != -1:
continue
# 次の頂点を追加
queue.append(next_v)
distance[next_v] = distance[v] + 1
# 頂点 u からの最大距離を返す
return max(distance)
# 頂点1からの最大距離
max_1 = bfs(1-1)
# 頂点N1+N2からの最大距離
max_N1N2 = bfs(N1 + N2 - 1)
print(max_1 + max_N1N2 + 1)
参考
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜 – Qiita
リンク
リンク
リンク
リンク