洛谷 P2661 信息传递（并查集 & 最小环）

嗯...

 

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

 

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

 

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

 

核心思想：

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

 

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int n, minn = 0x7f7f7f7f;
int f[200005], d[200005];

inline int find(int x){
    if(f[x] !=x ){
        int last = f[x];
        f[x] = find(f[x]);
        d[x] += d[last];
    }
    return f[x];
}

inline void check(int a, int b){
    int x = find(a), y = find(b);
    if(x != y){
        f[x] = y;
        d[a] = d[b] + 1;
    }
    else minn = min(minn, d[a] + d[b] + 1);
}

int main(){
    int t;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= n; i++){
        scanf("%d", &t);
        check(i, t);
    }
    printf("%d", minn);
    return 0;
}