AtCoder が提供しているABC（AtCoder Beginner Contest）315 のE問題をC++とPythonで解いてみました。ABC315は、2023年8月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Prerequisites（Difficulty : 921）
問題はリンク先をご覧ください。
グラフの問題と考えて、頂点1からの距離を求めます。ただし、可能な限り長い距離を求める必要があります。AtCoder Problems による Difficulty は 921 でした。
解答案
頂点1から到達可能な頂点について、頂点1からの距離を求めますが、可能な限り長い距離を求めます。入力例1のグラフは以下となります（頂点6は孤立しています）。
頂点1から距離1の頂点は、頂点2、3、4となります。頂点1からの距離2の頂点は、頂点5となりますが、頂点3は頂点2を経由した場合に距離が2となります。ここで可能な限り距離が長い順番に並べる必要があります。
今回の場合、5、3、4、2 や 3、5、２、4 が回答になります。
距離が長い順ではない、5、4、3、２も回答になりますが、5、2、3、4 のように条件を満たさない場合もあります。
C++ プログラム例（ABC315E）
DFS（7ー15行目）を使って距離を求めますが、より長い距離が見つかったときは距離を更新します（11行目で判断、12行目で更新）。
DFS を使った探索後に頂点1からの距離を配列 depth に格納してソートします（35ー41行目）。最後に距離が長い順番に頂点を出力します（43ー45行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> depth;
void dfs(int v, int d)
{
depth[v] = d;
for (auto next_v : G[v]) {
if (depth[next_v] < d + 1) {
dfs(next_v, d + 1);
}
}
}
int main()
{
int n;
cin >> n;
G.resize(n + 1);
depth.assign(n + 1, -1);
for (int i = 1; i <= n; ++i) {
int c;
cin >> c;
for (int j = 0; j < c; ++j) {
int p;
cin >> p;
G[i].push_back(p);
}
}
dfs(1, 0);
vector<pair<int, int>> result;
for (int i = 1; i <= n; ++i) {
if (depth[i] > 0) {
result.push_back(make_pair(-depth[i], i));
}
}
sort(result.begin(), result.end());
for (int i = 0; i < result.size(); ++i) {
cout << result[i].second << " \n"[i == result.size() - 1];
}
return 0;
}コンテストには上記のプログラムを提出しました。公式にあるユーザ回答で、より分かりやすい考え方が紹介されていました。
頂点1からDFSで探索することは同じですが、「帰りがけ順」に出力すれば、こちらもACとなります。
このブログでは、DFSを使う場合、各頂点に到達したかを配列 seen で管理しています。この配列で「行きがけ順」が分かります。今回は、dfs後に配列 finished の値を更新します（16行目）。finished を更新した順番が「帰りがけ順」となります。
「帰りがけ順」の配列 result から最初の頂点1を抜いて（38行目）、出力しました。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<bool> finished;
vector<int> result;
void dfs(int v)
{
for (auto next_v : G[v]) {
if (!finished[next_v]) {
dfs(next_v);
}
}
finished[v] = true;
result.push_back(v);
}
int main()
{
int n;
cin >> n;
G.resize(n + 1);
finished.assign(n + 1, false);
for (int i = 1; i <= n; ++i) {
int c;
cin >> c;
for (int j = 0; j < c; ++j) {
int p;
cin >> p;
G[i].push_back(p);
}
}
dfs(1);
result.pop_back();
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " \n"[i == result.size() - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC315E）
Pythonは、再帰関数の呼出回数に制約があります。sys.setrecursionlimit を使って増やしています（5行目）。C++の帰りがけ順の回答を移植しました。
"""AtCoder Beginner Contest 315 E"""
import sys
LIMIT = 2*10**5
sys.setrecursionlimit(LIMIT + 1)
result = []
def dfs(v):
for next_v in G[v]:
if not finished[next_v]:
dfs(next_v)
finished[v] = True
result.append(v)
n = int(input())
G = [[] for i in range(n + 1)]
finished = [False] * (n + 1)
for i in range(1, n + 1):
p = list(map(int, input().split()))
for j in range(1, len(p)):
G[i].append(p[j])
dfs(1)
result.pop(-1)
print(*result)こちらも「AC」と判定されました。
最後に
E問題は、D問題とDifficultyが逆転していました。問題を読んで難易度が分かり、E問題を解くことができました（結果的に、D問題は時間切れとなりましたが）。
グラフの問題は、当初まったく解けませんでした。進歩を感じると楽しく感じます。
引き続き ABC の問題を紹介していきます。
