AtCoder が提供しているABC（AtCoder Beginner Contest）296 のE問題をC++で解いてみました。ABC296は、2023年4月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Transition Game（Difficulty : 1285）
問題はリンク先をご覧ください。
強連結成分分解を使って解くことができました。AtCoder Problems による Difficulty は 1285 でした。
解答案
i → A[i] を辺とする有向グラフの問題として解くことができます。
青木君が Ki を指定します。この場合、i がグラフの閉路の頂点として含まれれば、高橋君が勝つことができます。i に到達する適当な x を選ぶことができるからです。それ以外の場合は高橋君の負けとなります。
最終的に有向グラフの閉路に含まれる頂点の個数を調べればよいことが分かります。これは、強連結成分分解と呼ばれるアルゴリズムで解くことができます。
強連結成分分解についての考え方は、こちらのページ、実装はこちらのページを参考にさせていただきました。
基本的な考え方は、以下となります。
- 有向グラフ G に対して、深さ優先探索（DFS）を行い、探索が終わった頂点の順番（order）を格納する。
- 枝を逆向きにした rG に対して、order が大きい頂点から深さ優先探索を行う。ある頂点から探索できる範囲は、同じ連結成分となる。
クラス StronglyConnectedComponents として実装しました。
class StronglyConnectedComponents {
private:
int n;
vector<vector<int>> G, rG;
vector<int> order;
vector<bool> seen;
public:
vector<int> component;
private:
void dfs(int v) {
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
order.push_back(v);
}
void rdfs(int v, int k) {
component[v] = k;
for (auto next_v : rG[v]) {
if (component[next_v] < 0) {
rdfs(next_v, k);
}
}
}
public:
StronglyConnectedComponents(int _n, vector<vector<int>> &_G, vector<vector<int>> &_rG) {
n = _n;
G = _G;
rG = _rG;
component.assign(n, -1);
seen.assign(n, false);
for (int v = 0; v < n; ++v) {
if (!seen[v]) {
dfs(v);
}
}
int k = 0;
reverse(order.begin(), order.end());
for (auto v : order) {
if (component[v] == -1) {
rdfs(v, k);
++k;
}
}
}
};コンストラクタに対して、頂点数、グラフG、枝を逆向きにした rG を渡すと、頂点 0 から |V| – 1 に対して、どの連結成分に属しているかを示す配列 component を更新します。コンストラクタと component だけを公開しています。
他にもメソッドを用意する実装が多いですが、今回はこのクラスで問題を解きます。
C++ プログラム例（ABC296E）
上で実装した StronglyConnectedComponents クラスを使います。クラスは頂点を 0 から処理するため、読み込んだ Ai の値をデクリメントしています（66行目）。
また、Ai と i が等しい場合は、i は高橋君の勝ちになります。この場合は枝として登録しません（73から74行目）。
StronglyConnectedComponents クラスのコンストラクタを呼び出した時点（81行目）で、各頂点がどの連結成分に含まれているのか、scc.component に格納されています。連結成分に含まれている頂点の個数が2個以上の場合、勝つ回数として、その頂点数を加えます（84、89行目）。
以下が、最終的なC++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
class StronglyConnectedComponents {
private:
int n;
vector<vector<int>> G, rG;
vector<int> order;
vector<bool> seen;
public:
vector<int> component;
private:
void dfs(int v) {
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
order.push_back(v);
}
void rdfs(int v, int k) {
component[v] = k;
for (auto next_v : rG[v]) {
if (component[next_v] < 0) {
rdfs(next_v, k);
}
}
}
public:
StronglyConnectedComponents(int _n, vector<vector<int>> &_G, vector<vector<int>> &_rG) {
n = _n;
G = _G;
rG = _rG;
component.assign(n, -1);
seen.assign(n, false);
for (int v = 0; v < n; ++v) {
if (!seen[v]) {
dfs(v);
}
}
int k = 0;
reverse(order.begin(), order.end());
for (auto v : order) {
if (component[v] == -1) {
rdfs(v, k);
++k;
}
}
}
};
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
}
vector<vector<int>> G(n);
vector<vector<int>> rG(n);
int result = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == i) {
++result;
} else {
G[i].push_back(a[i]);
rG[a[i]].push_back(i);
}
}
StronglyConnectedComponents scc(n, G, rG);
map<int, int> m;
for (int i = 0; i < n; ++i) {
++m[scc.component[i]];
}
for (auto e : m) {
if (e.second >= 2) {
result += e.second;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
かなり記事が長くなってしまいました。今回は、Python プログラムの紹介を省略します。
最後に
コンテスト中に、閉じている有向グラフの頂点の個数を調べればよいことは分かりましたが、具体的なコーディングができませんでした。強連結成分分解について調べるきっかけになりました。
引き続き ABC の問題を紹介していきます。
