并查集
|
1.5k 字
|
5 分钟

并查集

前言

今天根据书上的指引，想要学习最小生成树，然而蒟蒻在 OI WIKI 上学习的时候被告知：
前置章节是并查集。。。
于是蒟蒻便用了一天的时间 A 了三道黄题一道蓝题（其实相当于一道黄题……
所以今天蒟蒻过来总结一番

定义

并查集是一种树形结构，通过名字我们可以知道：
并：合并，查：查询，集：集合
就是合并和查询一个集合
也可以相当于是联通块之间的判断。
我们把一个联通快之间的点放入一个点集之中，
并查集就可以查询这个点是不是在集合中（不知道集合的去预（复）习高一课本

实现

我们看一个故事：
几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。
（来自于 OI WIKI）
我们的并查集就相当于是这个故事中的实现过程：
建立一棵树，将父亲自己的儿子放进儿子节点中
每次询问两个人是在哪一个家族（树）之中，就询问自己的父亲是否在家族（树）之中
如果两个人的某个祖先（c++意义上）相等，就相当于他们两个是在一个家族中的
但是，有一次，两个祖先对话，想将各自的家族合并到一起，这该怎么办。。。
好办！将一个祖先的爸爸改成另一个祖先就可以了，反正我们不在乎某一个节点的爸爸究竟是谁，显然我们只在乎两个人是否是同一个家族也就是需不需要去一(de)起(guo)祭(gu)拜(ke)。

朴素

查找：
就像上述操作一样，建立一棵树，将某些儿子们放进并查集，访问就可以知道是那颗树
合并：
也像上面一样，改父亲
在最开始的时候，我们是不知道谁是谁的爸爸的，那么就让他们每一个人都是一个小家族，当我们知道了谁是谁的爸爸之后，进行一次合并操作，就可以让两个人变成同一个祖先
但是，如果每一次查找都要向上跳到最上面的祖先或者每一次合并都需要合并 n/2 个点，那么复杂度将会是巨大的。。。

优化

路径压缩

路径压缩，顾名思义，就是将并查集查询的路径进行压缩
我们上面说到了，每一次查找都需要向上进行跳跃，一直跳到祖先一样（其实一般都需要直接爬到最上面
这样的复杂度真的很大
定义中说的是：我们要判断联通块，那么我们就把所有的儿子节点直接连向树根
之后再去判断就只需要 O（1）时间查询祖先了（虽然在预处理的时候不是 O1 但也快了不少

启发式合并

说实话我不知道为什么要去这个名字，感觉很难受并且我找不到名字和操作之中的关系
上面有说到，我们在合并的时候，是要将一个祖先改成另一个祖先的儿子的
那么如果 n 个点，n-1 个点是一个集合，1 个点是一个集合，我们将它合并，要把 n-1 个点的爸爸都改一改，会很累
但如果我们把 1 个点的祖先更改，就会很简单的呢！（假装很厉害的样子
所以，每一次我们进行合并之前，都记录一下联通块的点数
每一次合并取一次 min，就会优化

注：

其实启发式合并有没有无所谓，有的时候还可能增加你的时间复杂度（其实可能就是一个常数
在不用启发式合并只用路径压缩的复杂度其实也就是 mlogn 甚至说 ma(m,n)。。。
（所以我不会写启发式合并

代码

代码就以洛谷的板子了 P3367

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int fa[maxn];//父节点
int find(int x)
{
    //查找
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
void unionset(int x,int y)//合并
{
    x=find(x);
    y=find(y);
    fa[x]=y;//祖先的更改
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    //初始化，自己是一个小家族
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>z>>x>>y;
        if(z==1)
        {
            unionset(x,y);
        }
        if(z==2)
        {
            if(find(x)==find(y))cout<<'Y'<<endl;
            else cout<<'N'<<endl;
        }
    }
    return 0;
}

带权并查集

其实带权并查集和普通的并查集没有什么太大的不同，只是在我们每一次改变权值的时候都改一下到根节点的距离罢了
（其实我也不会，明天学会再改博客）

可持久化并查集

（不会，以后再说。。。）
（这种东西应该是要在以后重新发博客的。。。如果你以后在我的博客之中翻到了。。。就不要让我回来改博客了。。。很累的。。。）

经典题

NOI2015 程序自动分析
JSOI2008 星球大战
NOI2001 食物链
NOI2002 银河英雄传说
UVA11987 Almost Union-Find

应用

最小生成树（马上要去写）和 LCA 最近公共祖先（写完了，可以看）

尾声

很大一部分借鉴了 OI WIKI
侵权勿喷。。。（我非盈利 aaa
good bye

上一篇
下一篇