浅谈并查集

Otachi · 2025-11-13 13:58:58 · 算法·理论

并查集具有码量小、时间复杂度优秀、适用范围广等特点，是一种常考的数据结构。

算法介绍

并查集本质上就是一个森林，每棵树就代表一个集合，树中的节点表示集合中的元素。

并查集，顾名思义，需要支持两个操作：

查询：查找一个元素属于哪个集合。
合并：合并两个集合。

初始化

定义一个数组 fa，存储节点的父亲节点。

初始时，每个节点的父亲节点都是自己，所以 fa_i=i。

查询

首先需要搞清楚的是，若节点 i 是所属树的根，当且仅当 i 满足 i=fa_i。

那么就可以通过递归的方式实现了。对于要查询的 i，每次查找它的父亲 fa_i。当满足 i=fa_i 时说明 i 就是根节点，返回 i 即可。

时间复杂度是 O(h)，其中 h 为树高。因为这完全就是暴力跳树。

唉这里就可以用到路径压缩了。

虽然有人认为这种方法和记忆化搜索差不多，但两者本质还是完全不同的。

我们的 fa_i 存的是 i 的父亲节点。但是在查找的过程中，我们并不需要 i 的父亲节点，我们只需要 i 所在树的根节点。

因此与其让这棵树的高度变幻莫测，还不如让这棵树只有两层。第一层是根节点，第二层就是子节点。

:::warning[\mathbb{LITTLE \ TIPS}]{open} 注：在有合并的情况下，想要维持两层是很难的。但是这不代表路径压缩没有用，它确实可以有效地减少树的层数。树的层数越小意味着时间复杂度就越小。 :::

合并

其实合并是很好想的。只需要把一棵树的树根连到另一棵树的根就行了。

这与路径压缩一起用是考场上的常用写法。在 Tarjan 大神的论文中说明了这种方法单次的最坏时间复杂度是 O(\log n)；在姚期智大神的论文中明确了这种方法单次的平均时间复杂度是 O(\alpha(n))，其中 \alpha(n) 为反阿克曼函数，几乎可以视作常数。

最坏时间复杂度 O(\log n)，这还是不够优秀。所以我们可以使用启发式合并。

启发式合并是一种乱搞充分发扬人类智慧的做法。它基于一种常识：把小的移动到大的比把大的移动到小的省力。所以我们可以通过维护每个树的节点个数 siz，每次把节点个数小的移动到节点个数大的即可。

这样单次的时间复杂度是稳定的 O(\alpha (n))，证明可见这里。

代码实现

例题：P3367 【模板】并查集

初始化

for(int i=1;i<=n;i++)
{
    fa[i]=i;
    siz[i]=1;
}

查询

int find(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=find(fa[x]);
}

合并

void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy)return;
    if(siz[fx]<siz[fy])swap(fx,fy);
    fa[fy]=fx;
    siz[fx]+=siz[fy];
}

并查集的应用

反集

你说得对，关押罪犯确实是一道很经典的反集题目，但是肯定会有人说可以用二分图做。所以我搬出了食物链，有本事你给我发明一个三分图出来。

例题：P2024 [NOI2001] 食物链

这道题就可以用反集来做。反集就是用 i' 甚至 i'' 来维护与 i 有关系的点。

这道题也是一样。可以用 i' 表示 i 的食物，i'' 表示 i 的天敌。

那么分类讨论第一种说法和第二种说法：

如果是第一种情况，那么有两种情况是谎话：

会触发三次合并操作：

合并 x 和 y。
合并 x 的食物和 y 的食物。
合并 x 的天敌和 y 的天敌。

如果是第二种情况，那么有两种情况是谎话：

会触发三次合并操作：

合并 x 和 y 的天敌。
合并 x 的食物和 y。
合并 x 的天敌和 y 的食物。

那么如何表示 i 的食物和 i 的天敌呢？用 i+n 和 i+n+n 表示就可以了。

给出关键代码：

while(m--)
{
    int op,x,y;
    scanf("%d%d%d",&op,&x,&y);
    if(x>n||y>n)
    {
        ans++;
        continue;
    }
    if(op==1)
    {
        if(find(x+n+n)==find(y)||find(x+n)==find(y))
        {
            ans++;
            continue;
        }
        merge(x,y);
        merge(x+n,y+n);
        merge(x+n+n,y+n+n);
    }
    else
    {
        if(find(x)==find(y)||find(x)==find(y+n))
        {
            ans++;
            continue;
        }
        merge(x+n,y);
        merge(x+n+n,y+n);
        merge(x,y+n+n);
    }
}

权值并查集

权值并查集，顾名思义，其实就是通过并查集维护一些信息。

例题：P1196 [NOI2002] 银河英雄传说

考虑通过维护节点到根节点的距离 front_i。那么考虑每次操作时 front_i 的变化：

初始时，front_i=0。
当查询一个值时，对于每个遍历到的 i，front_i 都要加上它的父节点的 front 值。
合并时，要更新被合并的 j 的 front 值，要把它加上 siz_i。所以我们要维护两个值：到根节点的距离 front_i 和所属集合的大小 siz_i。

那么最终 i 与 j 的距离呢？很显然是 |front_i-front_j|-1。

给出关键代码：

int find(int x)
{
    if(x==fa[x])
        return x;
    int fx=find(fa[x]);
    front[x]+=front[fa[x]];
    return fa[x]=fx;
}
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    front[fx]+=siz[fy];
    siz[fy]+=siz[fx];
    siz[fx]=0;
    fa[fx]=fy;
}

玄学优化

例题：P4145 上帝造题的七分钟 2 / 花神游历各国

首先区间开方有一个经典的 trick，就是一个小于 10^{12} 的数在开方 6 次后就可以变成 1，没有开方的价值了。

因此我们可以暴力遍历开方，通过并查集跳过无用的元素，更快的找到下一个有价值的元素。这里我用了树状数组维护区间和。

给出关键代码：

while(m--)
{
    int op,l,r;
    scanf("%d%d%d",&op,&l,&r);
    if(l>r)swap(l,r);
    if(op==0)
    {
        for(int i=l;i<=r;)
        {
            add(i,(ll)sqrt(a[i])-a[i]);
            a[i]=(ll)sqrt(a[i]);
            fa[i]=(a[i]<=1?i+1:i);
            i=(fa[i]==i?i+1:find(fa[i]));
        }
    }
    else
    {
        printf("%lld\n",query(r)-query(l-1));
    }
}

总结

并查集的用处还是挺广的。有些知识限于能力无法介绍，所以只讲了那么多，还请大家见谅。

参考文献

本文所有图片均来自 OI-Wiki 并查集。