题解 P4089 【[USACO17DEC]The Bovine Shuffle】

· · 题解

首先，我们理解一下题意

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

给你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;
}