题解 P2661 【信息传递】

KING__Arthur · 2018-10-29 11:59:03 · 题解

看到很多大佬写并查集 的写法，但很多大佬都写的很麻烦，感觉并查集可以不压行写的很短（蒟蒻太弱不敢压行）

很显然，对于有向图，如果考虑从每一个点出发，用DFS求出它到自己的距离，如果遍历了N个点仍未便利到自己，则该点不在环中。但是这样做的复杂度非常感人……如果没有分析错的话最坏应该是O(n^2m)。

聪明的我们又发现，此题两个小破孩之间没有权值，所以只要写一个普通并查集就可以解决这个问题。

只要先打一段并查集模板（没有路径压缩优化的）

inline int find(int x) //正常的并查集
{
    if (fa[x]!=x)
      return find(fa[x]);
    else
      return x;
}

然后在添加一个变量deep，用来记录此时遍历了几个小盆友了

inline int find(int x,int &deep) //一边遍历，一边记录此时是第几轮
{
    deep++;//记录深度（第几个人，考虑到并查集是棵树，所以可以记成deep）
    if (fa[x]!=x)
      return find(fa[x],deep);
    else
      return x;
}

然后开始遍历，记得每次开始前先讲deep置零（用ans来记录全局最小值）很多大佬用并查集时都开了数组记录环的长度，其实不用这么麻烦。

for (int i=1;i<=n;i++) 
    {
        int deep=0,now;
        cin>>now;//当前这个小盆友传递对象是谁
        if(find(now,deep)==i)//如果又遍历到他自己，就是说他在这个环里
          ans=min(ans,deep);//记录当前环的长度
        else
          fa[i]=now;
    }

然后完美结束~~

但并查集求最小环不是很快，机房测试时10个点跑了1.3S，同机房红名大佬用拓扑+DFS用了0.37S，我太弱了，但好处是代码短。。。。

完整代码：

前面说的很清楚了，所以代码不带解释！！！

#include <iostream>
#include <cstdio>
using namespace std;
int n, fa[1000001],ans=121432423;
int find(int x,int &deep) 
{
    deep++;
    if (fa[x]!=x)
      return find(fa[x],deep);
    else
      return x;
}
int main () 
{
    freopen("message.in","r",stdin);
    freopen("message.out","w",stdout)；
    cin>>n;
    for(int i=1;i<=n;i++);
      fa[i]=i；
    for (int i=1;i<=n;i++) 
    {
        int deep=0,now;
        cin>>now;
        if(find(now,deep)==i)
          ans=min(ans,deep);
        else
          fa[i]=now;
    }
    cout<<ans<<endl;
    return 0;
}

据说抄题解会变棕