C - Find it! Editorial by cirno3153
より簡単な実装公式解説にあるように、頂点を一つ任意に取り、そこから移動し続けることでサイクルに到達することができます。
ところで、予めサイクル内から始めることができれば、実装はより簡単になります。
これは、最初に \(N\) 回移動しておくことで必ず達成できます。
また、 \(A\) の先頭にダミーを増やして1-indexedにしておくなどの工夫により、実装はより簡潔になります。
Kotlinの実装例
import java.util.*
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val A = IntArray(N + 1){if (it == 0) 0 else sc.nextInt()}
var now = 1
repeat(N) {now = A[now]}
val B = mutableListOf<Int>()
do {
B.add(now)
now = A[now]
} while(B[0] != now)
println(B.size)
println(B.joinToString(" "))
}
}
Pythonの実装例
N = int(input())
A = list(map(int, ("0 " + input()).split()))
now = 1
for _ in range(N): now = A[now] # 予めN回移動する
B = [now]
while B[0] != A[now]:
now = A[now]
B.append(now)
print(len(B))
print(*B)
なお、サイクルは強連結成分であることから、SCCを用いることでもACできます。
C++の実装例
#include <atcoder/scc>
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
atcoder::scc_graph graph(++n);
vector<int> a(n);
for (int i = 1; i < n; ++i) {
cin >> a[i];
graph.add_edge(i, a[i]);
}
auto scc = graph.scc();
for (auto &s : scc) {
int now = s[0], len = s.size();
if (len == 1) continue;
cout << len << '\n';
for (int i = 0; i < len; ++i) {
cout << now << ' ';
now = a[now];
}
return 0;
}
}
余談
\(N\) 頂点 \(N\) 辺の有向グラフであって、各頂点から丁度一つの辺が出ているものをFunctional Graphと呼びます。 競技プログラミングにおいてFunctional Graphは頻出なので、予め性質を覚えておくと得する場面があるかもしれません。
posted:
last update: