AtCoder が提供しているABC（AtCoder Beginner Contest）293 のD問題をC++とPythonで解いてみました。ABC293は、2023年3月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Tying Rope（Difficulty : 830）
問題はリンク先をご覧ください。
グラフと考えて、それぞれの連結成分の形がリングになるか一本になるか判断する問題です。AtCoder Problems による Difficulty は 830 でした。
解答案
問題文を読むと、ロープの端の色に関する記述が気になります。問題の入力にも、ロープの端の色が指定されています。
「同じ色の端が複数回結ばれることはありません」とありますので、結ばれたロープの形は、リング状になるか、一本状のどちらかになります。
結果的に、ロープの端は関係なく、Ai と Ci を結ぶ辺から成る無向グラフと考えて、各連結成分について、頂点と辺の数を調べる問題に帰着します。
- 連結成分に含まれる頂点と辺の数が同じであれば、リング状となる。
- 連結成分に含まれる頂点と辺の数が異なる場合、一本状となる。
結果的に、ABC292 D問題と似た構造となります。
C++ プログラム例（ABC293D）
DFS（深さ優先探索：Depth-First Search）を用いて、グラフの連結成分に含まれる頂点と辺の個数について調べます。
初めて訪れる頂点で、頂点と辺の個数を増やします（15、16行目）。この変数は、連結成分毎にリセットしています（41、42行目）。辺の数は、グラフを登録するときに合わせて配列 n_of_edge に代入して、使っています（7、16、34行目）。
各連結成分毎に頂点と辺の数を確認して、解答の変数を更新します（44－48行目）。
以下が、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;
char b, d;
cin >> u >> b >> v >> d;
e[u].push_back(v);
e[v].push_back(u);
++n_of_edge[u];
}
int result_ring = 0;
int result_not_ring = 0;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
vertex = 0;
edge = 0;
dfs(i);
if (vertex != edge) {
++result_not_ring;
} else {
++result_ring;
}
}
}
cout << result_ring << " " << result_not_ring << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC293D）
C++ の場合と同じで、プログラムは、ABC292 D問題と同じ構造となります。
再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています（5行目）。回数は余裕をみて設定しました。
"""AtCoder Beginner Contest 293 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, b, v, d = input().split()
u = int(u)
v = int(v)
e[u].append(v)
e[v].append(u)
n_of_edge[u] += 1
result_ring = 0
result_not_ring = 0
for i in range(1, n + 1):
if not seen[i]:
vertex = 0
edge = 0
dfs(i)
if vertex != edge:
result_not_ring += 1
else:
result_ring += 1
print(result_ring, result_not_ring)こちらも「AC」と判定されました。
最後に
問題に記載されている「端の色」は、「同じ色の端が複数回結ばれることはありません」という制約が重要でした。この制約により形が、リング状か一本状になります。ロープの番号を頂点と考えて、グラフの問題に帰着させることができました。
このように視点を変えて解けると楽しくなります。
引き続き ABC の問題を紹介していきます。
