题解 P2661 【信息传递】

· · 题解

我们可以考虑用并查集来做这道题。

我们在连接一个点到另一个点之前，先用并查集判断是否构成一个环，如果是的话，我们就可以记录下这个答案，然后维护最小的答案。

那么，如果构成一个环的话，怎么记录它的长度呢？

我们可以先定义一个变量cnt，在并查集获取祖先的函数中使cnt的值加1，最后函数结束时就能得到这个环的长度了qwq！

同时，如果构成了一个环，就不需要把这个环的结尾接上，否则会陷入死循环！！

最后附上短短的代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 200010;
int n, fa[N], ans = 0x3f3f3f3f;
int get (int x, int &cnt) { //cnt记录环的长度 
    cnt ++;
    if (fa[x] == x) return x;
    else return get(fa[x], cnt);
}
int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        fa[i] = i;
    for (int i = 1; i <= n; i ++) {
        int cnt = 0, f;
        scanf("%d", &f);
        if (get(f, cnt) == i) {
            ans = min(ans, cnt); //维护最小的环 
        }else
            fa[i] = f;
    }
    printf("%d", ans);
    return 0;
}