P1543 SZP

题意

每名同学都监视着另一名同学，要求选出尽量多的人，使得 被选出 的每个人 至少有一名 监视她的同学没有被选中，输出最多选多少人。

思路

一人套一人，首选拓扑。首先一个同学如果没被人监视，那么她就不可能被选择，于是将她入队。
因为她没被选，所以她所监管的人就有人（她自己）监管了，因此她监管的人便可以被选择。

考虑出现环的情况，形如 $A$ 监管 $B$，$B$ 监管 $C$，$C$ 监管 $A$，选择任意一人将她视为 不被选择，之后按上面的步骤即可，这里容易发现，在环中被选取的人数占环中人数的一半。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,ans=0;
int son[N];
int in[N];
int f[N];
int flag[N];
queue<int>q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>son[i],in[son[i]]++;
	for(int i=1;i<=n;i++)
		if(!in[i])q.push(i),flag[i]=1;
	while(!q.empty())
	{
		int u=q.front(),v=son[u];
		q.pop();
		flag[u]=1;
		if(f[u])
		{
			ans++;
			in[v]--;
			if(!in[v])q.push(v);
		}
		else if(!f[v])q.push(v),f[v]=1;
	}
	for(int i=1;i<=n;i++)
		if(!flag[i])
		{
			int s=0;
			for(int j=i;!flag[j];j=son[j])
				s++,flag[j]=1;
			ans+=s/2;
		}
	cout<<ans;
	return 0;
 }