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

时间:2022-10-30 17:09:22

题目来源:洛谷

题目描述

n 个同学(编号为 1n )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学。

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

输入输出格式

输入格式:

 

2行。1行包含1个正整数 n ,表示 n 个人。

 

 

输出格式:

 

1个整数,表示游戏一共可以进行多少轮。

 

输入输出样例

输入样例#1:
5
2 4 2 3 1
输出样例#1:
3

说明

样例1解释

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

游戏的流程如图所示。当进行完第3 轮游戏后, 4号玩家会听到 2 号玩家告诉他自己的生日,所以答案为 3。当然,第 3 轮游戏后, 2号玩家、 3 号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。

对于 30%的数据, n200;

对于 60%的数据,n 2500;

对于 100%的数据, n200000。

解析:

在想了半天之后还是去看了题解,我真tm弱。

写这道题看标签有个并查集,结果实际上是坑人的。这哪里是并查集啊喂?!虽说也是吧,但是与其说是并查集,倒不如说是用并查集这种思想记录一下数据之间的关系。。。

这个关系,其实就是某节点信息当前传递到的节点的位置而已,可以把它看成一条链,我们称其为“信息传递链”。

这道题其实是求最小环。。。其他最小环算法也可以搞定。


 

这道题稍微有点难以理解,因为如果要用并查集做,要稍微做一点转换。

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

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

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

PS:如果把本题看作一张有向图,那么自始至终这张图都不会出现一个环,因为如果连接任意一个环,之后查找这个环中某一结点的父节点时,就会陷入死循环。

 

参考代码:

 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