题解：P2661 [NOIP2015 提高组] 信息传递

· · 题解

P2661 [NOIP2015 提高组] 信息传递

刚学并查集，花了挺久才想清楚这题为什么能用并查集，写个题解整理思路。

题目大意

给定一个 n 个点 n 条边的有向无权图（不保证联通），求最小环的长度。

保证每个点有且仅有 1 条出边，不存在自环。

思路分析

其实这题完全没必要用并查集，由于每个点出度都为 1 的性质，直接 dfs 加上时间戳就可以通过。不过我们这里主要讨论并查集做法。

样例的图如下：

不难确定答案是 3，但是我们要想这个答案是如何得出的。

首先建立并查集并初始化，开始每个点各自属于一个集合。同时我们要设一个数组 dis 用来计算结点 i 到其根节点的图上距离，初始值为 0。

（3，4 放反了）。

然后我们添加 (1,2) 这条边，将 1 与 2 所在的树合并。

接着我们添加 (2,4),(3,2) 这两条边，操作后如下：

（使用路径压缩后，3 在连接到 2 时会连到其根节点 4 的位置）。

然后我们要添加 (4,3) 这条边，这时候我们发现 3 和 4 已经在一个集合里了。因此我们就可以确定有一个环了。

但我们要如何确定最小环的长度呢？这时候 dis 数组就派上用场了。先上代码：（代码中的 v 数组就是上文的 dis 数组）

inline int find(int x) {
    if (father[x] != x) {
        int lst = father[x];
        father[x] = find(father[x]);
        v[x] += v[lst];
    }
    return father[x];
}
inline void merge(int x,int y) {
    int p = find(x);
    int q = find(y);
    if (p != q) {
        father[p] = q;
        v[x] = v[y] + 1;
    }else{
        ans = min(ans,v[x]+v[y]+1);
    }
}
int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) father[i] = i;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        merge(i,t);
    }
    cout << ans << '\n';
    return 0;
}

当我们添加一条边时，如果这条边连接的两个点 u,v 不在一个集合（一个环）里，则合并后，令 dis_u = dis_v + 1（v 到祖先的图上距离加上这条边的长度 1），同时在查找的过程中重新更新查找路径上的所有 dis 值。而如果 u 和 v 已经在一个集合里，则代表找到了一个环，则直接统计答案为 dis_u + dis_v + 1（u 到自己祖先的图上距离加上 v 到自己祖先的图上距离再加上当前这条边的长度 1）。

为什么只更新 u 的值呢？因为边是有向边，所以添加这条边时只有从 u 到 v 的路而没有从 v 到 u 的路。

需要注意的是，这种方法只适用于所有点出度仅有 1 的有向图，因为只有保证 u 唯一时，u,v 同时处在一个集合才等同于 u,v 在环上。

可能以上说的有些琐碎，建议自己手玩一下样例可能就清楚了。

AC Code

#include <bits/stdc++.h>
using namespace std;
int n,ans = 0x3f3f3f3f;
int father[200005],v[200005],cnt;
inline int find(int x) {
    if (father[x] != x) {
        int lst = father[x];
        father[x] = find(father[x]);
        v[x] += v[lst];
    }
    return father[x];
}
inline void merge(int x,int y) {
    int p = find(x);
    int q = find(y);
    if (p != q) {
        father[p] = q;
        v[x] = v[y] + 1;
    }else{
        ans = min(ans,v[x]+v[y]+1);
    }
}
int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) father[i] = i;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        merge(i,t);
    }
    cout << ans << '\n';
    return 0;
}