P2661 信息传递 DFS

一个人要想知道自己的生日，就意味着信息的传递是成环的，因为每轮信息只能传递一个人，传递的轮数就等于环的大小

环的大小就等于环中的两个点到第三个点的距离之和加一，我们就可以在使用并查集时，维护每个点到某个确定点的距离

不妨令这个确定点为当前点的祖先，在同一个集合中，所有的点拥有共同的祖先，因此可以确定环的大小

有可能有多个环，最小的环就是最小的轮数

 #include <bits/stdc++.h>

 using namespace std;

 int f[];

 int l[];    //到祖先的距离

 int minn = <<;

 int fa(int a){

     if(f[a] != a){

         int father = f[a];

         f[a] = fa(f[a]);

         l[a] += l[father];

     }

     return f[a];

 }

 bool check(int a,int b){

     return fa(a) == fa(b);

 }

 void link(int a,int b){

     if(!check(a,b)){

         f[fa(a)] = fa(b);

         l[a] = l[b]+;

     }

     else    //已经成环

         minn = min(minn,l[a]+l[b]+);

 }

 int main()

 {

     int n;

     cin>>n;

     for(int i=;i<=n;++i)

         f[i] = i;

     for(int i=;i<=n;++i){

         int ans;

         cin>>ans;

         link(i,ans);

     }

     cout<<minn;

     return ;

 }

巴特西

P2661 信息传递 DFS

最新文章

热门文章