P2661 信息传递[最小环+并查集]

题目来源：洛谷

题目描述

有

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入输出格式

输入格式：

共第

输出格式：

输入输出样例

输入样例#1：

5
2 4 2 3 1

输出样例#1：

说明

样例1解释

P2661 信息传递[最小环+并查集]

游戏的流程如图所示。当进行完第

对于

本题所谓的信息传递，实际上每次传递就相当于在有向图中连一条边，在并查集中记录父节点，由于并查集带权，我们开一个数组d[]记录一下就好了。

而当某个节点得知自己的信息时，说明在有向图中构成了一个环。而题目便是要求我们求一个最小环了。

注意不要把前驱和后继搞混了。。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #define N 200010
12 using namespace std;
13 int fa[N],d[N],ans;
14 int get(int x)
15 {
16     if(x!=fa[x])
17     {
18         int pre=fa[x];
19         fa[x]=get(fa[x]);
20         d[x]+=d[pre];//将之前节点到父节点的距离传递 
21     }
22     return fa[x];
23 }
24 void query(int x,int y)
25 {
26     int a=get(x),b=get(y);
27     if(a!=b)
28     {
29         fa[a]=b;
30         d[x]=d[y]+1;//连接一条边 
31     }
32     else
33     {
34         ans=min(ans,d[x]+d[y]+1);//注意此处并没有连成一个环! 
35     }
36 }
37 int main()
38 {
39     int n,x;
40     scanf("%d",&n);
41     for(int i=1;i<=n;i++) fa[i]=i;
42     ans=0x7fffffff;
43     for(int i=1;i<=n;i++){
44         scanf("%d",&x);
45         query(i,x);
46     }
47     printf("%d\n",ans);
48     return 0;
49 }

2019-05-26 12:59:29

秒客网

P2661 信息传递[最小环+并查集]

题目来源：洛谷

题目描述

输入输出格式

输入输出样例

说明

相关文章

P2661 信息传递[最小环+并查集]

题目来源：洛谷

题目描述

输入输出格式

输入输出样例

说明

解析：

参考代码：

相关文章