洛谷 P2661 信息传递(并查集 & 最小环)

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

嗯...

 

题目链接:https://www.luogu.org/problemnew/show/P2661

 

这道题和一些比较水的并查集不太一样,这道题的思路就是用并查集来求最小环...

 

首先,如果我们把题目中的每一个同学都看成是一个点,并且信息只能由 i 给 T[i],所以可以看成是一个有向图,并且当自己的信息别人告诉自己的时候,说明这个有向图已经成为了一个环了。而要求游戏可以进行几轮,就是要求最小环。

 

核心思想:

假如说信息由A传递给B,那么就连一条由A指向B的边,同时更新A的父节点,A到它的父节点的路径长也就是B到它的父节点的路径长+1。这样我们就建立好了一个图,之后信息传递的所有环节都按照这些路径。游戏结束的轮数,也就是这个图里最小环的长度。如果有两个点祖先节点相同,那么就可以构成一个环,长度为两个点到祖先节点长度之和+1,最后取min就好。

 

AC代码:

洛谷 P2661 信息传递(并查集 & 最小环)洛谷 P2661 信息传递(并查集 & 最小环)
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int n, minn = 0x7f7f7f7f;
 8 int f[200005], d[200005];
 9 
10 inline int find(int x){
11     if(f[x] !=x ){
12         int last = f[x];
13         f[x] = find(f[x]);
14         d[x] += d[last];
15     }
16     return f[x];
17 }
18 
19 inline void check(int a, int b){
20     int x = find(a), y = find(b);
21     if(x != y){
22         f[x] = y;
23         d[a] = d[b] + 1;
24     }
25     else minn = min(minn, d[a] + d[b] + 1);
26 }
27 
28 int main(){
29     int t;
30     scanf("%d", &n);
31     for(int i = 1; i <= n; i++) f[i] = i;
32     for(int i = 1; i <= n; i++){
33         scanf("%d", &t);
34         check(i, t);
35     }
36     printf("%d", minn);
37     return 0;
38 }
AC代码