AtCoder が提供しているABC（AtCoder Beginner Contest）288 のC問題をC++とPythonで解いてみました。ABC288は、2023年2月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Don’t be cycle（Difficulty : 436）
問題はリンク先をご覧ください。
グラフが閉路を持つ条件を考察します。AtCoder Problems による Difficulty は 436 でした。
解答案
問題で問われているように、与えられたグラフに閉路がないか探索します。今回の問題は、向きがありませんが（無向グラフ）、有向グラフの閉路については、ABC285 D問題で扱っています。
その頂点を通ったか（seen）と通り切ったか（finished）をフラグとして分けて管理しているため、閉路を検出しても、その先を探索しません。このため、この閉路を検出する方法でもうまくいきます。
C++ プログラム例（ABC288C）
基本的なプログラムの構造は、ABC285 D問題と同じです。ただし、無向グラフを扱うため、逆流を防ぐために親の頂点を探索関数 dfs の第2引数として渡しています。
解答となる変数 result は、探索関数 dfs で更新するため、グローバル変数としました。
#include <bits/stdc++.h>
using namespace std;
#define N 200001
vector<vector<int>> e(N);
vector<bool> seen(N, false);
vector<bool> finished(N, false);
int result = 0;
void dfs(int v, int p)
{
seen[v] = true;
for (auto next_v : e[v]) {
if (next_v == p) {
continue;
}
if (seen[next_v]) {
if (!finished[next_v]) {
++result;
}
} else {
dfs(next_v, v);
}
}
finished[v] = true;
}
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);
}
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
dfs(i, -1);
}
}
cout << result << endl;
return 0;
}公式解説を参考に別解を紹介します。
閉路が無いということは、各連結成分の頂点個数 N’ に対して、辺が N’ – 1 本しかないことと同値になります。公式解説では、数式で説明していますが、いくつかグラフの絵を描くことによっても確認することができます。
これらより、解答は M ー N ＋（連結成分の個数）となります。
連結成分の個数は、ABC284 C問題でも求めています。以下は、このアイデアに従ったプログラムとなります。こちらの方がすっきりと書けています。
#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);
}
int result = m - n;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
++result;
dfs(i);
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC288C）
Python では、連結成分を求める解法を採用しました。ABC284 C問題を流用しました。また、再帰関数の呼び出し回数の上限を増やしています（2-5行目）。
"""AtCoder Beginner Contest 288 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 = m - n
for i in range(1, n + 1):
if not seen[i]:
result += 1
dfs(i)
print(result)こちらも「AC」と判定されました。
最後に
ABC288は、予告されたようにD問題から難易度が上がりました。D問題のDifficultyは、1757でした。今の私の実力では解説することが難しく、C問題までの解説としました。
引き続き ABC の問題を紹介していきます。
