【AtCoder】ABC309 – D問題について解説【Python】

そまちょブログのそまちょ（@somachob）です。

この記事は、AtCoder Beginner Contest 309 の D問題についての解説です。

D – Add One Edge
幅優先探索
参考

D – Add One Edge

問題へのリンク

入力例１をもとに解説します。

見出し

3 4 6
1 2
2 3
4 5
4 6
1 3
6 7

入力を受け取ります。

グラフの問題なので、グラフで受け取ってます。

管理しやすいように、頂点は ‐１で受け取ります。

頂点１は０、頂点２は１、頂点３は２、…というようになります。

# 入力
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]]
"""

入力の受け取りについて、わからない場合は次の記事を参考にしてください。

【Python】input の使い方

幅優先探索

この問題は、次の２つの距離を足したものに１を足したものを解答すればいいことになります。

頂点１からの最大距離
頂点N1＋N2からの最大距離

これがわかれば、頂点１からの幅優先探索と頂点N1＋N2からの幅優先探索をしてその最大値に１を足せばいいです。

幅優先探索について、解説した記事も参考にしてください。

基本的な幅優先探索は、次のようなコードになります。

０から幅優先探索をして０からの距離を 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

これをもとに頂点１と頂点N1＋N2からの最大距離を足したものに１を足したものが答えになります。

これを実装したものが次のコードになります。

幅優先探索を関数にして、その最大の距離を返す関数を実装して、頂点１と頂点N1＋N2からの最大距離を取得しています。

実装の関係上、頂点番号は実際の頂点－１になっていることに注意してください。

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)

# 頂点１からの最大距離
max_1 = bfs(1-1)

# 頂点N1＋N2からの最大距離
max_N1N2 = bfs(N1 + N2 - 1)

print(max_1 + max_N1N2 + 1)

参考

BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜 – Qiita

リンク