AtCoder が提供しているABC（AtCoder Beginner Contest）292 のD問題をC++とPythonで解いてみました。ABC292は、2023年3月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Unicyclic Components（Difficulty : 579）
問題はリンク先をご覧ください。
ABC292 D問題 Unicyclic Components
グラフの連結成分が含む頂点と辺をカウントする問題です。AtCoder Problems による Difficulty は 579 でした。
解答案
与えらたグラフの連結成分に含まれる頂点の個数と辺の本数が等しいか調べます。連結成分については、ABC284 C問題でコードを紹介しました。
上記の基本的なコードに、各連結成分毎に頂点（vertex）と辺（edge）をカウントするコードを加えていきます。
C++ プログラム例（ABC292D）
初めて訪れる頂点で、頂点と辺の個数を増やします（15、16行目）。この変数は、連結成分毎にリセットしています（39、40行目）。辺の数は、グラフを登録するときに合わせて配列 n_of_edge に代入して、使っています（7、16、33行目）。
各連結成分毎に頂点と辺の数を確認しています（42－44行目）。
以下が、C＋＋プログラムとなります。基本的なグラフのコードからの差分を背景色を変更しています。
#include <bits/stdc++.h>
using namespace std;
#define N 200001
vector<vector<int>> e(N);
vector<bool> seen(N, false);
vector<int> n_of_edge(N, 0);
int vertex;
int edge;
void dfs(int v)
{
seen[v] = true;
++vertex;
edge += n_of_edge[v];
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);
++n_of_edge[u];
}
bool result = true;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
vertex = 0;
edge = 0;
dfs(i);
if (vertex != edge) {
result = false;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC292D）
Python 版は、C++ 版を移植しました。再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています（5行目）。回数は余裕をみて設定しました。
"""AtCoder Beginner Contest 292 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)
def dfs(v):
global vertex, edge
seen[v] = True
vertex += 1
edge += n_of_edge[v]
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)
n_of_edge = [0] * (n + 1)
for i in range(m):
u, v = map(int, input().split())
e[u].append(v)
e[v].append(u)
n_of_edge[u] += 1
result = True
for i in range(1, n + 1):
if not seen[i]:
vertex = 0
edge = 0
dfs(i)
if vertex != edge:
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
グラフの探索は、基本的にDFSを使っています。だいぶ慣れてきました。
引き続き ABC の問題を紹介していきます。
