codevs : 传送门
Description
上帝手中有着N 种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。
每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的
世界元素能够限制它，这样上帝就可以保持对世界的控制。由于那个著名的有关于上帝能不能制造一块连自己
都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找
你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2N) 级别的算法。虽然上帝拥有无限多
的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。
题解
把$A[ i ]$ 当作 $f[ i ]$ 即父节点
dfs找环 + 断环 + 重连
只需找到环上的任意两个点记录即可
找到了$x， y$ ， 并且$A_x = y$
断环： 让找到的两个点之间的边断开， 从子节点开始$dp$， 算出投放 $x$时的最大值即 $f[x][1]$
重连： 当然不可能真的重连，只需要让 $x$ 不被投放， 并且在处理$y$时， $y$的子节点无需限制它， 因为已经有$x$在限制了
相当于重连
记得手工栈， 不然会RE
注意一个点组成的环需要一些特判，不然会WA
代码
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
#define R register
using namespace std; const int N = 1e6 + 1e3; int n, m, fa[N], vis[N];
int f[N][], pos1, pos2, eg;
int tot, head[N]; struct edge {
int to, nxt;
}e[N << ]; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if( c== '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} int lev;
int st_x[N];
int st_nt[N];
int st_tmp[N]; #define x st_x[lev]
#define nt st_nt[lev]
#define tmp st_tmp[lev] void find_cir(int u) {
st_x[] = u;
lev = ;
start:;
vis[x] = ;
nt = fa[x];
if(vis[nt]) {
pos1 = x; pos2 = nt;
}
else {
st_x[lev + ] = nt;
lev++;
goto start;
}
end:;
if((--lev)) goto end;
} int st_i[N]; #define i st_i[lev] void dp(int u) {
st_x[] = u;
lev = ;
start:;
tmp = ;
f[x][] = f[x][] = ;
vis[x] = ;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
st_x[lev + ] = nt;
lev++;
goto start;
end:; f[x][] = f[x][] + max(f[nt][], f[nt][]);
tmp += max(f[nt][], f[nt][]);
}
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
f[x][] = max(f[x][], + tmp - max(f[nt][], f[nt][]) + f[nt][]);
}
if(--lev) goto end;
} void dp2(int u) {
st_x[] = u;
lev = ;
start:;
tmp = ;
f[x][] = f[x][] = ;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
st_x[lev + ] = nt;
lev++;
goto start;
end:; f[x][] = f[x][] + max(f[nt][], f[nt][]);
if(x == pos2 && pos1 != pos2) f[x][] = f[x][] + max(f[nt][], f[nt][]);
tmp += max(f[nt][], f[nt][]);
}
if(x == pos2 && pos1 != pos2) {
f[x][]++;
if(--lev) goto end;
}
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
f[x][] = max(f[x][], + tmp - max(f[nt][], f[nt][]) + f[nt][]);
}
if(--lev) goto end;
} #undef x
#undef i
#undef nt
#undef tmp int work(int x) {
int maxn = ;
find_cir(x);
dp(pos1);
maxn = f[pos1][];
dp2(pos1);
maxn = max(maxn, f[pos1][]);
return maxn;
} int main()
{
n = rd;
int ans = ;
rep(i, , n) fa[i] = rd, add(fa[i], i);
rep(i, , n) if(!vis[i]) ans += work(i);
printf("%d\n", ans);
}