算法1
(周期性) $O(N)$
显然从点 $1$ 出发遍历 $K$ 条边可能会走进环(包含自环)里。
若能走进环里,我们可以用取余来找到我们最后会到达哪个点;
若不能走进环里,最多也只会遍历 $O(N)$ 条边
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int n; ll k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> s;
vector<int> ord(n+1, -1);
int c = 1, l = 0; // c: 环的长度 l: 遍历到最后一个点的下标
{
int v = 1;
while (ord[v] == -1) {
ord[v] = s.size();
s.push_back(v);
v = a[v-1];
}
c = s.size() - ord[v];
l = ord[v];
}
if (k < l) cout << s[k] << '\n';
else {
k -= l;
k %= c;
cout << s[l+k] << '\n';
}
return 0;
}
算法2
(倍增) $O(N\log K)$
也可以用倍增来加速暴力
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const int D = 60;
const int MX = 200005;
int to[D][MX];
int main() {
int n; ll k;
cin >> n >> k;
rep(i, n) {
cin >> to[0][i];
to[0][i]--;
}
rep(i, D-1)rep(j, n) to[i+1][j] = to[i][to[i][j]];
int v = 0;
for (int i = D-1; i >= 0; --i) {
ll l = 1ll<<i;
if (l <= k) {
v = to[i][v];
k -= l;
}
}
cout << v+1 << '\n';
return 0;
}