图 DFS

tarjan做法显然是违背出题人意图的。

本题限制了每个点只有一条出边，所以不存在复杂回路，如果成环，只存在简单环。

于是可以直接DFS，如果成环，就把整个回路都置为回路上点的数量。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
int a[N], ans[N], c;
// ans[i]表示从i出发能到达多少个点
bool vis[N];
int dfs(int u) {
    vis[u] = 1;
    int v = a[u];                    //导向点
    if (vis[v]) {                    //访问过
        if (ans[v] == 0) c = v;      //成环
        return ans[u] = ans[v] + 1;  //连接
    } else
        return ans[u] = dfs(v) + 1;  //深度+1
}
void check(int u, int v) {  //把整个回路修正
    ans[u] = ans[v];
    if (a[u] != v) check(a[u], v);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) if (!vis[i]) {
        c = -1;  //回路的起点，dfs跑完以后ans[c]就记录了环上有多少个点
        dfs(i);
        //如果成环 整个环上都是简单路径可收纳的点
        if (c != -1) check(c, c);
    }
    int res = 0;
    cout << res << '\n';
    return 0;
}