AtCoder が提供しているABC（AtCoder Beginner Contest）292 のE問題をC++とPythonで解いてみました。ABC292は、2023年3月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Transitivity（Difficulty : 1272）
問題はリンク先をご覧ください。
ある頂点から到達可能な頂点をカウントする問題となります。AtCoder Problems による Difficulty は 1272 でした。
解答案
最初に以下のプログラムを試しました。
基本的な考えは以下です。
- 登録された辺を格納する（21、39行目）。
- 訪れた頂点を配列に記憶する（15、28、43行目）。
- 訪れた頂点（親側）とつながっている頂点（子供側）で、登録されていない辺を格納する。そのときに解答も増やす（17-23行目）。
#include <bits/stdc++.h>
using namespace std;
#define N 2001
vector<vector<int>> e(N);
vector<bool> seen(N, false);
set<pair<int, int>> path;
vector<int> this_path;
int result = 0;
void dfs(int v)
{
seen[v] = true;
this_path.push_back(v);
for (auto next_v : e[v]) {
for (auto prev_v : this_path) {
if ((prev_v != v)&&(prev_v != next_v)
&&(path.find(make_pair(prev_v, next_v)) == path.end())) {
++result;
path.insert(make_pair(prev_v, next_v));
}
}
if (!seen[next_v]) {
dfs(next_v);
}
}
this_path.pop_back();
}
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);
path.insert(make_pair(u, v));
}
for (int i = 1; i <= n; ++i) {
this_path.clear();
seen.assign(N, false);
if (!seen[i]) {
dfs(i);
}
}
cout << result << endl;
return 0;
}このプログラムは、51ケース中 4ケースがTLE（Time Limit Exceeded）判定となりました。WA（Wrong Answer）判定のテストケースはありませんでした。残念ながら実行時間を短くする工夫が必要なようです。
以下は、公式解説を参考にしました。
最終的なグラフは、初期状態において任意の頂点 x から到達可能な頂点を終点とする有向辺がすべて貼られている状態になります。
つまり、各頂点から到達可能な頂点数を調べて、辺の数（M）を引けば解答となります。
C++ プログラム例（ABC292E）
以下が、C＋＋プログラムとなります。基本的なグラフのコードからの差分を背景色を変更しています。
#include <bits/stdc++.h>
using namespace std;
#define N 2001
vector<vector<int>> e(N);
vector<bool> seen(N, false);
int result = 0;
void dfs(int v)
{
seen[v] = true;
for (auto next_v : e[v]) {
if (!seen[next_v]) {
++result;
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);
}
for (int i = 1; i <= n; ++i) {
seen.assign(N, false);
dfs(i);
}
cout << result - m << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC292E）
Python のグラフの問題は、C++ 版をそのまま移植しています。今回もそのままの移植です。再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています（5行目）。回数は余裕をみて設定しました。
"""AtCoder Beginner Contest 292 E"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)
def dfs(v):
global result
seen[v] = True
for next_v in e[v]:
if not seen[next_v]:
result += 1
dfs(next_v)
n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
for i in range(m):
u, v = map(int, input().split())
e[u].append(v)
result = 0
for i in range(1, n + 1):
seen = [False] * (n + 1)
dfs(i)
print(result - m)こちらも「AC」と判定されました。
最後に
この問題は、TLE判定のまま時間切れでした。
公式解説を参考にした最終的なプログラムは、E問題の割にシンプルになりました。また、C++ 版の実行時間も短くなりました（50m秒程度）。
引き続き ABC の問題を紹介していきます。
