自动搬运

查看原文

来自洛谷，原作者为

	QAQ永动机 QAQ

搬运于2025-08-24 21:56:22，当前版本为作者最后更新于2019-07-07 11:26:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，我们理解一下题意

每一个位置上都有一个牛。每头牛都会变换

给你n个数，分别是a1，a2……an。ai表示每一次变换位置为i的牛会变到位置为ai的地方。变换后，有的位置上有多个牛，那么他们下一次变换，这个位置上的所有牛都会这么变。

问无论几次变化后，一共有多少个位置上有牛

看看样例：

in:

4
3 2 1 3

out:

3

画个图，理解一下

$\tiny\texttt{箭头表示从位置几跳到位置几}$

欸？这不就是个有向图吗？

我们来画一画：

结合样例，我们来看看

输出了3，是哪3个？是1，2，3三个位置。那么为什么4号没有牛呢？我们可以发现因为1，2，3入度都大于0，唯独4小于0.哦？难道和入度有关？

猜想

我们不妨有一个猜想：如果有一个点，他的收入可以维持他的支出，那么这个点上一直有牛。也就是

if(入度-出度>=0){
	ans++;
 }

这就对了吗？我们欣喜的发现样例过了。提交一下——WA

这是为什么呢？来看看这组数据——

in:

1 1 2

输出应该是1，可是以我们这样判断就是2

QAQ泪奔

猜想2

我们可以发现，导致这种错误的原因是第一轮3给了2一头牛，可是第二轮3没有牛了，从而让2后面每轮得到的牛为0。就是因为3入度为0，所以"养不起"2

所以我们可以猜想：如果一个点入度为0，那么这个点指向的点入度--。（大家听起来应该很费劲，用伪代码给大家理解)

if(in[f[i]]==0)
{
	in[i]--;
{

f[i]存储的是指向自己的点

可是f[i]里可能有多个点，怎么存呢？

我们用一个队列存储入度为0的点，然后一个循环减去，最后找到入度不为0的就好了。

这不就是拓扑吗？

实现

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],ans;
int out[100005],in[100005];
queue<int> q;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		
		in[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0){
			q.push(i);
		}
	}
    
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		in[a[tmp]]--;
		if(in[a[tmp]]==0)
		{
			q.push(a[tmp]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]!=0)
		{
			ans++;
		}
	}

	cout<<ans;
   return 0;
}