AtCoder が提供しているABC（AtCoder Beginner Contest）284 のC問題をC++とPythonで解いてみました。ABC284は、2023年1月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Count Connected Components（Difficulty : 193）
問題はリンク先をご覧ください。
ABC284 C問題 Count Connected Components
与えられたグラフの連結成分の個数を求める問題です。AtCoder Problems による Difficulty は、193 でした。
解答案
連結成分の個数は、以下の方法で求めることができます。
- グラフとして扱う。DFS（深さ優先探索：Depth-First Search）で探索する。
- グラフとして扱う。BFS（幅優先探索：Breadth-First search）で探索する。
- Union-Find として扱う。
この問題では、私が一番慣れているDFSを使いました。コード自体がこの典型的な問題を解くための説明になっていると考えています。
C++ プログラム例（ABC284C）
グラフは、ABC270 C問題、ABC277 C問題でも取り扱いました。探索を行う dfs は基本的な素の実装です。その頂点を訪れたか配列 seen で管理して、訪れていない場合は、連結成分の個数を増やします。
以下が、C++ のプログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define N 101
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 = 0;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
++result;
dfs(i);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC284C）
Python 版も C++ 版と同じ実装ですが、注意があります。環境にも依存しますが、再帰関数の呼出回数の上限が1000回に設定されている場合が多いようです。これは、ABC269 問題D、ABC277 C問題で問題となりました。今回の場合、頂点の数 N が100以下であるため、再帰関数の呼び出し回数を増やす必要はありませんでした。
以下が、Python のプログラムとなります。
"""AtCoder Beginner Contest 284 C"""
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 = 0
for i in range(1, n + 1):
if not seen[i]:
result += 1
dfs(i)
print(result)こちらも「AC」と判定されました。
最後に
この問題の Difficulty は 193 でした。問題の内容を考えると、解けた人が多かったように感じます。グラフに不慣れな人は、もう少し多くいる印象でした。AtCoder の参加者全体のレベルが高いのだと思います。
引き続き ABC の問題を紹介していきます。
