自然地想到 \(i\) 向 \(a_i\) 连边。
随便造一组强一点的数据：
10
3 1 2 10 10 8 9 20 8 2
图大概长这样
容易发现每个 \(i\) 有且仅有 \(1\) 条出边。
-
发现图中 \(1,2,3\) 这 \(3\) 个点组成了一个环。在这个环上，每个人都能做到自己心仪的位置上，所以这个环对答案的贡献是这个环包含的点的数量。
-
当一个点 \(>n\) 的时候，就没有办法接着连下去了，于是乎出现了一条链。这条链上每 \(<=n\) 的点都能坐到心仪的位置，对答案的贡献是链上的点数 \(-1\)。
-
当两条链有重合部分的时候，一部分人就不能坐上心仪的座位了。这个重合部分其实就是一棵有向树的树根。从这里出发，只有 \(1\) 条链上的人可以找到心仪的座位，所以对答案的贡献就是以这里为终点的最长链的点数。
于是，题做完了。
由于需要求以 \(k\) 为终点的最长链，所以还要建一个反图。
#include <bits/stdc++.h>
#define gt getchar
#define pt putchar
#define ll long long
const int MAXN = 2e5 + 5;
ll read() {
ll x = 0, f = 1;char ch = gt();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
return x * f;
}
std::vector<ll> z[MAXN], fz[MAXN];
bool vis[MAXN];//记录i有没有计入答案
ll in[MAXN];
void add_edge(ll s, ll e) {
z[s].push_back(e);//正图
fz[e].push_back(s);//反图
}
ll n;
void dfs(ll now, ll len, ll &res) {
//当前搜到了编号为now的点，从根走到这里的长度为len，最终答案为res
vis[now] = true;
res = std::max(res, len);//更新答案
for (int i = 0; i < fz[now].size(); i++) {
//继续沿着反边往回走
dfs(fz[now][i], len + 1, res);
}
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
ll x = read();
add_edge(i, x);//建边
in[x]++;
}
ll ans = 0;
for (int i = n + 1; i <= n + n; i++) {
//每一个 >n 的点都可能是一条链的末端，倒着往前搜
ll res = 0;
dfs(i, 0, res);
ans += res;//更新答案
}
std::queue<ll> q;//拓扑排序
for (int i = 1; i <= n; i++) {
if(!vis[i] && in[i] == 0) {
q.push(i);
vis[i] = true;
}
}
while(q.size()) {
ll now = q.front();
q.pop();
for (int i = 0; i < z[now].size(); i++) {
ll j = z[now][i];
in[j]--;
if(!in[j]) {
q.push(j);
vis[j] = true;
}
}
}
//没有被排序到的点在环里
for (int i = 1; i <= n; i++) {
if(!vis[i]) {
++ans;
}
}
std::cout << ans << '\n';
return 0;
}