AtCoder が提供しているABC（AtCoder Beginner Contest）376 D問題をC++とPythonで解いてみました。ABC376は、2024年10月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Cycle（Difficulty : 743）
問題の詳細は、リンク先をご覧ください。
BFSで各頂点までの最短距離を求めます。AtCoder Problems による Difficulty は 743 でした。
解答案
頂点1を含む最小の閉路の辺数を求める問題です。
- 頂点1から、それぞれの頂点までの最短距離を求めます。BFS（幅優先探索：Breadth-First search）で求めることができます。
- それぞれの頂点から頂点1に辺があるか調べれば、最小の閉路の辺数が分かります。
C++ プログラム例（ABC376D）
多くは一般的な定番コードです。次の頂点が1であれば最小値を更新するコードが差分となります（26ー28行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> G(n + 1);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
vector<int> dist(n + 1, -1);
queue<int> que;
que.push(1);
dist[1] = 0;
int result = INF;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (next_v == 1) {
result = min(result, dist[now] + 1);
}
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
if (result == INF) {
result = -1;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC376D）
Python版も基本的な考え方は同じです。BFS のキューは、collections.deque を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 376 D"""
from collections import deque
INF = 10 ** 9 + 1
n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(m):
a, b = map(int, input().split())
G[a].append(b)
dist = [-1] * (n + 1)
que = deque()
que.append(1)
dist[1] = 0
result = INF
while que:
now = que.popleft()
for next_v in G[now]:
if next_v == 1:
result = min(result, dist[now] + 1)
if dist[next_v] == -1:
que.append(next_v)
dist[next_v] = dist[now] + 1
if result == INF:
result = -1
print(result)こちらも「AC」と判定されました。
最後に
グラフに慣れてきたのか、この問題は簡単に感じました。コンテスト参加を続けている効果を感じて、うれしくなります。
引き続き ABC の問題を紹介していきます。
