AtCoder が提供しているABC（AtCoder Beginner Contest）287 のC問題をC++とPythonで解いてみました。ABC287は、2023年1月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Path Graph?（Difficulty : 466）
問題はリンク先をご覧ください。
グラフが一本道の形になるか判定する問題です。AtCoder Problems による Difficulty は 466 でした。
解答案
問題文に、「単純無向グラフ」と「パスグラフ」の説明がありました。パスグラフについて、「グラフがひとつの線分の形になる」と解釈しました。
以下の条件を満たすグラフがパスグラフになります。これは、グラフの形をいくつか書いていくと分かりました。
- 頂点の個数（N）に対して、辺の個数（M）は、N – 1 個となる。つまり N – 1 = M となる。
- すべての頂点の次数は2以下となる。両端は次数1となり、残りが次数2となる。
- 全体が連結している。
上2つの条件は、グラフとして入力されたデータから判断ができます。最後のひとつは、連結個数を求める問題となります。これは ABC284 C問題でも紹介しました。
C++ プログラム例（ABC287C）
方針に従い、プログラムしました。連結個数を求めるための探索には、慣れている DFS（深さ優先探索：Depth-First Search）を使いました。関数 dfs は、基本的な実装から変更していません。
パスグラフとなるかを Bool 型の変数 result で管理します。初期値を true にして、条件を満たさない場合に false にします。最終的に result に従い、”Yes” か “No” を出力します。
#include <bits/stdc++.h>
using namespace std;
#define N 200001
vector<vector<int>> e(N);
vector<bool> seen(N, false);
void dfs(int v)
{
seen[v] = true;
for (auto next_v : e[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
bool result = true;
if (n - 1 != m) {
result = false;
}
for (int i = 1; i <= n; ++i) {
if (e[i].size() > 2) {
result = false;
}
}
dfs(1);
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
result = false;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC287C）
Python 版も、C＋＋ プログラムを移植しました。グラフの表現と関数 dfs の実装は、ABC284 C問題を流用しました。また、再帰関数の呼び出し回数の上限を増やしています（2-5行目）。
"""AtCoder Beginner Contest 287 C"""
import sys
LIMIT = 2 * 10 ** 5 + 1
sys.setrecursionlimit(LIMIT)
def dfs(v):
seen[v] = True
for next_v in e[v]:
if not seen[next_v]:
dfs(next_v)
n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
seen = [False] * (n + 1)
for i in range(m):
u, v = map(int, input().split())
e[u].append(v)
e[v].append(u)
result = True
if n - 1 != m:
result = False
for i in range(1, n + 1):
if len(e[i]) > 2:
result = False
dfs(1)
for i in range(1, n + 1):
if not seen[i]:
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
パスグラフとなる条件を抽出することが難しい問題でした。
なお、コンテスト本番では、条件「すべての頂点の次数は2以下となる」が抜けていてもAC判定をもらうことができました。恥ずかしながら、わたくしの最初のプログラムもこの条件が抜けていました。
コンテスト後に、Twitter でこのことがコメントされて、すぐにテストケースが追加されていました。運営のみなさまの努力に感謝したいと思います。
引き続き ABC の問題を紹介していきます。
