https://codeforces.com/gym/105257/problem/C

题意：
给出长为 n 数组 ai,你需要找到长为n的数组 bi(1 ≤ i ≤ n, 1 ≤ bi ≤ 2n) 满足 ∀i ̸= j,bi̸=bj且∀i,b=i或bi=ai。最大化bi=ai的个数并输出最大值。

首先此题较难想到建边写 考虑i向a[i]建边，会形成三种图
1.有向树且为单链
2.一个环
3.由于每个点最多一条出边所以为内向基环树森林（三包含二）
对于有向树树链的深度就是最大值我们建反边，可以发现一条链上最多一个大于n号点（因为每个点建边起点小于等于n指向的点可能编号大于n，而此点无法指向其他点了），从每个编号大于n的来查找最长链计入答案即可。
对于基环树，我们进行拓扑排序，判断有几个点没有出过队，它们一定在环上，计入答案即可。

# include <bits/stdc++.h>
using namespace std;
//#define x first
//#define y second
int n;
const int N=3e5+10;
vector<int>v[N];
vector<int>vf[N];
int in[N];
bool st[N];
int res=0;
void dfs(int u,int d,int &res)
{
    if(u<=n)
    {
    st[u]=1;
    res=max(res,d);
    }
    for(auto x:vf[u])
    {
    dfs(x,d+1,res);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    int x;
    cin>>x;
    v[i].push_back(x);
    vf[x].push_back(i);
    in[x]++;
    }
    int ans=0;
    for(int i=n+1;i<=2*n;i++)
    {
    res=0;
    dfs(i,0,res);   
    ans+=res;
    }
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(!st[i]&&!in[i])
        {
        st[i]=1;
        q.push(i);
        }
    }
    while(!q.empty())
    {
    int t=q.front();
    q.pop();
    for(auto x:v[t])
    {
        in[x]--;
        if(in[x]==0)
        {
        st[x]=1;
        q.push(x);
        }
    }   
    }
    for(int i=1;i<=n;i++)
    {
    if(!st[i])
    ans++;
    }
    cout<<ans<<endl;
}