[模版]并查集

· · 题解

题目分析

传送门

题面要你资瓷 2 个操作：

算法介绍

你可能需要知道的前置知识：树，时间复杂度的表示。

树的话嘛，不懂也没事啦

先来看看第一个操作怎么实现，否则实现第二个操作就是天方夜谭。

如图，这里有两个集合 Crinity（简称 c）和 arius（简称 a），我们要把这几个点塞到一起去。

注：你当然不用担心怎么存集合的名字，因为用不着。大不了用 1，2\dots 这些数字代替就是了。

一个比较简单的想法是：我用一个数组存下所有点是哪个集合的。然后每次遍历一遍数组，把 a 这个集合里的元素全部标记成属于集合 c，就像这样：

但是我们会发现，假如几乎全都是操作 1，这样做的复杂度将会被卡到 O(nm)，但看一眼数据范围，那显然爆炸了。怎么办呢？

其实，这并不意味着这个想法完全是错的。如果我们能找出几个固定的点来代替整个集合，那我只要改这几个点就好了。

那我要拿什么去维护它呢？

答案简直就是呼之欲出了——树。

树就是像这样的东西。然后我们有一个很好的性质，就是我把这个 c1 和 a1 一连，就 O(1) 的把两棵树，也就是两个集合合并了。

但这样一个行为，又带来几个问题：

1. 怎么去存这些树啊？

要是你用二维数组存，不说别的，空间都开不下。要是硬开的话，直接不给你编译了！

于是，有一个很好的想法，就是说，我新开一个数组 f_i，每个点都存那个图里跟它连线，而且在它上面的那个点（按照术语来说，就是它的父亲）不就好了么？反正那个所谓“父亲”也是唯一的！而对于每棵树最上面那个点（按照术语来说，就是树的根节点），直接让它的父亲是自己得了~

其实这样，我们不就会写操作 2 了吗，判一判是不是拥有同一个根节点不就好了~

2. 你要合并的时候，我给的不一定是树的根节点啊？万一不是根节点怎么办？直接连这两个点不就乱套了？

这里说明一下，之所以不能直接连，是因为这样：比如说给的点是 c3 和 a3。那我把 c3 连 a3 身上，就像这张图一样，那 c 这棵树就倒过来了。不然，你 c3 有两个父亲，一棵树有两个根节点，那还行？复杂度先不说，你连维护这棵树倒过来都很难做到！其实你真写出来也是TLE

所以，我肯定得找到祖先。那祖先怎么判定呢？显然，假设 k 是祖先，那肯定有 f_k=k 嘛！

那我只要发现，我的父亲不是根节点，那就把这个问题丢给父亲，让它去判断我的祖父是不是根节点嘛！就这样，我们可以递归的解决这个问题：

int find(int k){ //返回的值就是根节点的编号
    if(f[k]==k) return k; //现在这个点就是根节点
    else{
        int ans=find(f[k]); //把问题丢给父亲解决~ 
        return ans;
    }
}

所以合并和判断也就好解决啦：

void Union(int a,int b){ //操作1
    f[find(a)]=f[find(b)]; //根节点连线，简单粗暴
}
bool check(int a,int b){ //操作2
    if(find(a)==find(b)) return true;//让我看看根节点一不一样！
    return false;
}

于是就能就能轻松写出代码啦~

完结撒花 \dots 了吗？

如果你实现完了，你交上去，发现你获得了 50 分的好成绩！

合着跟暴力毫无区别呗，跑了跑了

冷静下来，考虑这个图：

我每次让你查 10，你就得遍历一遍，数据一大，又变回 O(nm) 了！

那怎么办呢？

我会写 LCT！

我会写平衡树！

其实也很简单：使用路径压缩。

那么，什么是路径压缩呢？

我们发现，在图中，如果我们发现 10 的父亲是 1，那我直接把他的父亲更改为 1，那么下次遇到 10，我就不用再搜一整条链了。

同理，搜索过程中，把 2 到 9 的父亲改一下，我们就不用再搜一遍了。

那么图就会变成这样了：

路径压缩的代码：

//其他一样啦~
int find(int k){
    if(f[k]==k) return k;
    else{
        f[k]=find(f[k]); //修改父亲，即路径压缩
        return f[k];
    }
}

但是我们当然不能只局限于通过此题，带来一个看起来很玄学的优化。也可以说是一种优化思想。

启发式合并

思考一下，并查集的复杂度当然是与树的高度息息相关。

比如说这张图：

我把 1 连 2 上，树就有 5 层。但反过来做，我就只有 4 层了。既然有要操作这么多次，那么它总是有作用的。

那每次合并时，我总把矮的树合并到高的上面，就能有效加速了。

代码如下：

void Union(int a,int b){
    //ht是树的高度（只管根节点的就好了） 
    a=find(a),b=find(b);
    if(ht[a]<ht[b]) swap(a,b);//启发式合并 
    ht[b]=max(ht[b],ht[a]+1);
    f[a]=f[b];
}

初始树的高度都是 1。

时间复杂度与正确性证明

Tarjan 大神曾经证明过，其复杂度不会超过 O(m\log n)（只使用路径压缩）。而其均摊复杂度，姚期智大神曾证明为 O(m\alpha(n))。

其中 \alpha(n) 是反阿克曼函数。可以视为一个常数。因为如果它不能视为常数的时候神威太湖之光都得跑到天荒地老具体的说，在 n \le 10^{{2^{10}}^{19279}} 的时候，都有 \alpha(n) \le 5，当成常数没有不妥。

使用启发式合并后，最低复杂度稳定为 O(m\alpha(n)) ，不会被卡。对于这些复杂度的证明，由于其过于繁杂，这里略去。具体证明可以看此处：

https://oi-wiki.org//ds/dsu-complexity/ 。

使用路径压缩和 scanf，printf 后可以将每个测试点控制在 250 ms 内。而加上启发式合并后，每个测试点被控制在 225 ms 内。

代码实现

#include<bits/stdc++.h>
using namespace std;
int f[2000010],ht[2000010];
int a,b,c,n,m;
int find(int k){
    if(f[k]==k) return k;
    else{
        f[k]=find(f[k]);
        return f[k];
    }
}
void Union(int a,int b){
    a=find(a),b=find(b);
    if(ht[a]>ht[b]) swap(a,b);
    ht[b]=max(ht[b],ht[a]+1);
    f[a]=b;
}
bool check(int a,int b){
    if(find(a)==find(b)) return true;
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i,ht[i]=1;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&c);
        if(a==1) Union(b,c);
        else{
            if(check(b,c)==true) printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

并查集的进阶用法

*：该拓展中，路径压缩毫无意义。

完结撒花。