「USACO17DEC」The Bovine Shuffle

题意：小明面前站着一排 $0<n<100001$ 个人，每次小明下令变换位置时，当前 $i$ 的所有人都会到 $a _i$。他想知道有多少位置，无论他连续下几次命令一直都有人。

一道水题。

很明显就是找环嘛。

从 $i$ 到 $a _i$ 连一条边，在这个有向图上，如果一个点在环上，那么这个点一直都有人。

证明：一开始每个点都只有一头牛，保证环上每个点都有牛。环上的每个点在一次命令后，所有的牛会来到下一个点，即每个点都会先失去牛，在获得上一个点来的牛，所以环上每个点一直都能有牛。

求环拓扑排序即可。

环上的点不会进入队列，所以直接拓扑排序统计入队次数，用 $n$ 减去入队次数就是环上的点的个数。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=2e5;
int n,a[maxn],indgr[maxn];
int head[maxn],cnt,ans;
queue<int> q;
struct node
{
	int next;
	int to;
}e[maxn<<2];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void topsort()
{
	for(int i=1;i<=n;i++)
		if(!indgr[i])
		{
			q.push(i);
			ans++;
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(--indgr[v]==0)
			{
				q.push(v);
				ans++;
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		add(i,a[i]);
		indgr[a[i]]++;
	}
	topsort();
	printf("%d",n-ans);
	return 0;
}