题目大意：给定一张有向图，每一个点有且仅有一条出边，要求若一个点x扔下去，至少存在一个保留的点y，y的出边指向x，求最多扔下去多少个点

首先原题的意思就是支配关系 我们反向考虑 求最少保留的点 要求一个点若扔出去 则必须存在一个保留的点指向它

于是这就是最小支配集 只是因为是有向图 所以一个点要么选择 要么被子节点支配 所以就仅仅剩下2个状态了

设f[x]为以x为根的子树选择x的最小支配集 g[x]为不选择x的最小支配集

然后因为是基环树林 所以我们选择一个环上的点 拆掉它的出边 设这个点为x 出边指向的点为y 讨论

1.若x选择 则y一開始就是被支配状态 g[y]初值为0 求一遍最小支配集

2.若x不选 正常求最小支配集就可以

两种情况取最小值计入ans 最后输出n-ans就可以

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 1001001

#define INF 0x3f3f3f3f

using namespace std;

struct abcd{

	int to,next;

	bool ban;

}table[M];

int head[M],tot;

int n,p,conquered,ans,a[M],f[M],g[M],fa[M];//f 选 g 被支配

bool v[M];

void Add(int x,int y)

{

	table[++tot].to=y;

	table[tot].next=head[x];

	head[x]=tot;

}

void DFS(int x)

{

	v[x]=1;

	if(v[a[x]])

		p=x;

	else

		DFS(a[x]);

}

void Tree_DP(int x)

{

	int i;

	f[x]=1;

	g[x]=INF;

	v[x]=1;

	if(x==conquered)

		g[x]=0;

	for(i=head[x];i;i=table[i].next)

		if(!table[i].ban&&table[i].to!=fa[x])

		{

			fa[table[i].to]=x;

			Tree_DP(table[i].to);

			g[x]+=min(f[table[i].to],g[table[i].to]);

			g[x]=min(g[x],f[x]+f[table[i].to]-1);

			f[x]+=min(f[table[i].to],g[table[i].to]);

		}

}

int main()

{

	int i;

	cin>>n;

	for(i=1;i<=n;i++)

		scanf("%d",&a[i]),Add(a[i],i);

	for(i=1;i<=n;i++)

		if(!v[i])

		{

			DFS(i);

			table[p].ban=1;

			conquered=a[p];

			Tree_DP(p);

			int temp=f[p];

			conquered=0;

			Tree_DP(p);

			temp=min(temp,g[p]);

			ans+=temp;

		}

	cout<<n-ans<<endl;

}