专栏文章

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

AAscnbeta
P2661题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqejiyv
此快照首次捕获于
2025/12/04 03:30
3 个月前
此快照最后确认于
2025/12/04 03:30
3 个月前
查看原文

P2661 [NOIP2015 提高组] 信息传递

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

题目大意

给定一个 nn 个点 nn 条边的有向无权图（不保证联通），求最小环的长度。
保证每个点有且仅有 11 条出边，不存在自环。

思路分析

其实这题完全没必要用并查集，由于每个点出度都为 11 的性质，直接 dfs 加上时间戳就可以通过。不过我们这里主要讨论并查集做法。
样例的图如下：
不难确定答案是 33，但是我们要想这个答案是如何得出的。
首先建立并查集并初始化，开始每个点各自属于一个集合。同时我们要设一个数组 disdis 用来计算结点 ii 到其根节点的图上距离，初始值为 00。
（3，4 放反了）。
然后我们添加 (1,2)(1,2) 这条边，将 11 与 22 所在的树合并。
接着我们添加 (2,4),(3,2)(2,4),(3,2) 这两条边，操作后如下：
（使用路径压缩后，33 在连接到 22 时会连到其根节点 44 的位置）。
然后我们要添加 (4,3)(4,3) 这条边，这时候我们发现 33 和 44 已经在一个集合里了。因此我们就可以确定有一个环了。
但我们要如何确定最小环的长度呢？这时候 disdis 数组就派上用场了。先上代码：（代码中的 vv 数组就是上文的 disdis 数组）
CPP
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,vu,v 不在一个集合（一个环）里，则合并后，令 disu=disv+1dis_u = dis_v + 1（vv 到祖先的图上距离加上这条边的长度 11），同时在查找的过程中重新更新查找路径上的所有 disdis 值。而如果 uu 和 vv 已经在一个集合里，则代表找到了一个环，则直接统计答案为 disu+disv+1dis_u + dis_v + 1（uu 到自己祖先的图上距离加上 vv 到自己祖先的图上距离再加上当前这条边的长度 11）。
为什么只更新 uu 的值呢？因为边是有向边，所以添加这条边时只有从 uu 到 vv 的路而没有从 vv 到 uu 的路。
需要注意的是，这种方法只适用于所有点出度仅有 11 的有向图，因为只有保证 uu 唯一时，u,vu,v 同时处在一个集合才等同于 u,vu,v 在环上。
可能以上说的有些琐碎，建议自己手玩一下样例可能就清楚了。

AC Code

CPP
#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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...