AtCoder が提供しているABC（AtCoder Beginner Contest）270 のC問題をC++で解いてみました。ABC270は、2022年9月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Simple path（Difficulty : 625）
問題はリンク先をご覧ください。
与えられたグラフから連結している頂点を探索する問題です。AtCoder Problems による Difficulty は、625 でした。
解答案
問題を解く方針を書きだします。
- 入力の読み込み（グラフの読み込み）
- グラフの探索
グラフの表現は、隣接リスト表現と呼ばれる、頂点 u から隣接している集合 vector e[u] を定義する方法がよく使われます。N 個の頂点と N – 1 個の辺を持つグラフの入力をするコードは以下となります。なおこの問題では向きを持たないため、両方向の登録をしています（10行目と11行目）。
vector<int> e[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
return 0;
}
グラフの探索は、DFS（深さ優先探索：Depth-First Search）を使う典型例となります。以下のコードでグラフの探索ができます。コードを読んで、動きを理解していただけたらと思います。
vector<int> e[N];
bool seen[N] = {false};
void dfs(int v)
{
seen[v] = true;
for (auto next_v : e[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}今回は、起点と終点が与えられて、その道筋を求めます。Ｃ問題としては難しいです。最終的なコードは以下となります。
C++ プログラム例（ABC270C）
#include <bits/stdc++.h>
using namespace std;
#define N 200001
vector<int> e[N];
bool seen[N] = {false};
vector<int> path;
bool stop;
void dfs(int from, int to)
{
if (!stop) {
path.push_back(from);
}
if (from == to) {
stop = true;
}
seen[from] = true;
for (auto next_v : e[from]) {
if (!seen[next_v]) {
dfs(next_v, to);
}
}
if (!stop) {
path.pop_back();
}
}
int main()
{
int n, x, y;
cin >> n >> x >> y;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
stop = false;
dfs(x, y);
for (int i = 0; i < path.size(); ++i) {
if (i != 0) {
cout << " ";
}
cout << path[i];
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
この C++ のプログラムを Python で書くのは、今のわたしでは難しいです。今回は、C++ のみの紹介とします。
最後に
グラフに慣れていない場合、C問題としては難しいと思います。
引き続き ABC の問題を紹介していきます。
