AtCoder が提供しているABC（AtCoder Beginner Contest）309 のD問題をC++とPythonで解いてみました。ABC309は、2023年7月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Add One Edge（Difficulty : 621）
問題はリンク先をご覧ください。
特定の2点から一番長い距離をそれぞれ求めて加えます。AtCoder Problems による Difficulty は 621 でした。
解答案
問題を読むと以下が分かります。
- 頂点 1、2、…、N1 のグラフは連結
- 頂点 N1+1、N1+2、…、N1+N2 のグラフは連結
- 上記2つは非連結
頂点 1 からの一番長い距離、頂点 N1+N2 からの一番長い距離を求めて加えて、1を加える（最後に操作で追加する辺）と解答になります。
C++ プログラム例（ABC309D）
特定の頂点（1 および N1＋N2）から連結しているすべての頂点への距離は、BFS を使って求めます。このコードはパターン化されています（18ー29行目、36ー47行目）。
それぞれの頂点からの一番長い距離を dist1、dist2 として求めます（31ー34行目、49ー52行目）。
最後に dist1、dist2 を加えて 1 を加えて出力します（54行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n1, n2, m;
cin >> n1 >> n2 >> m;
vector<vector<int>> G(n1 + n2 + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dist(n1 + n2 + 1, -1);
queue<int> que;
que.push(1);
dist[1] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
int dist1 = 0;
for (int i = 1; i <= n1; ++i) {
dist1 = max(dist1, dist[i]);
}
que.push(n1 + n2);
dist[n1 + n2] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
int dist2 = 0;
for (int i = n1 + 1; i <= n1 + n2; ++i) {
dist2 = max(dist2, dist[i]);
}
cout << dist1 + dist2 + 1 << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC309D）
Python では、Deque（Double-Ended QUEue）を使い BFS を実装します。考え方は、C++ と同じです。
"""AtCoder Beginner Contest 309 D"""
from collections import deque
n1, n2, m = map(int, input().split())
G = [[] for i in range(n1 + n2 + 1)]
for i in range(m):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
dist = [-1] * (n1 + n2 + 1)
que = deque()
que.append(1)
dist[1] = 0
while que:
now = que.popleft()
for next_v in G[now]:
if dist[next_v] == -1:
que.append(next_v)
dist[next_v] = dist[now] + 1
dist1 = max(dist[1:n1 + 1])
que.append(n1 + n2)
dist[n1 + n2] = 0
while que:
now = que.popleft()
for next_v in G[now]:
if dist[next_v] == -1:
que.append(next_v)
dist[next_v] = dist[now] + 1
dist2 = max(dist[n1 + 1:n1 + n2 + 1])
print(dist1 + dist2 + 1)こちらも「AC」と判定されました。
最後に
BFS を2回使うことは、問題を読んですぐに気づくことができました。当初まったくできなかったグラフの問題も解ける問題が増えてきました。
引き続き ABC の問題を紹介していきます。
