scy代码20250501：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N];
int a[N];bool vis[N];
int f[N][2];
void dp(int x,int rt)
{
    vis[x]=1;
    f[x][1]=1;f[x][0]=0;int t=N;
    for(int y:G[x])if(y!=rt)
    {
        dp(y,rt);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=max(f[y][0],f[y][1]);
        t=min(t,f[y][1]-f[y][0]);
    }
    if(t>0)f[x][1]-=t;
}

int main()
{
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &a[i]),G[a[i]].emplace_back(i);
    
	int ans=0;
    memset(vis,0,sizeof(vis));
	for(int i=1; i<=n; i++)if(!vis[i])
	{
		int x=a[i],y=i;while(x!=y)x=a[a[x]],y=a[y];
        y=a[x];
		dp(x,x);int tx1=f[x][1],tx0=f[x][0];
		if(y!=x)dp(y,y);int ty1=f[y][1],ty0=f[y][0];
		ans+= max(max(tx1,tx0),max(ty1,ty0));
	}
    printf("%d\n", ans);
    return 0;
}

scy旧代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N];
int dfn[N], tsp;
vector< pair<int,int> >roots;
void dfs(int x)
{
    dfn[x]=tsp;
    for(int y:G[x])
    {
        if(dfn[y]==0)dfs(y);
        else if(dfn[x]==dfn[y])roots.push_back({x,y});
    }
}
int f[N][2];
void dp(int x,int rt)
{
    f[x][1]=1;f[x][0]=0;int t=N;int y;
    for(y:G[x])if(y!=rt)
    {
        dp(y,rt);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=max(f[y][0],f[y][1]);
        t=min(t,f[y][1]-f[y][0]);
    }
    if(t>0)f[x][1]-=t;
}

int main()
{
    int n; scanf("%d", &n);
    for(int i=1,x; i<=n; i++)scanf("%d", &x),G[x].emplace_back(i);
    
    tsp=0; memset(dfn, 0, sizeof(dfn));
	for(int i=1;i<=n;i++)if(!dfn[i])tsp++,dfs(i);
    
	int ans=0;
	for(auto t:roots)
	{
		int x=t.first,y=t.second;
		dp(x,x);int tx1=f[x][1],tx0=f[x][0];
		dp(y,y);int ty1=f[y][1],ty0=f[y][0];
		ans+= max(max(tx1,tx0),max(ty1,ty0));
	}
    printf("%d\n", ans);
    return 0;