$"引言":$
这次一定写完,上几次的基环树与网络流都没写完,这次边学边写,我就不信了

• 进入正题

并查集

并查集是一种可以 动态维护 若干个不重叠的集合,并支持合并与查询的数据结构.

1. Get,查询一个元素属于哪一个大集合.
2. Merge,将两个集合合并成一个大集合.

为此,我们才有"代表元"法:
很好理解,即为每个集合选择一个固定的元素作为整个集合的代表.

于是,可以想象为一个森林代表一堆集合,而对应的,每棵树对应一个集合,每个树根即为代表

所以我们用 $f{a}_i$ 代表节点 $i$ 的父亲,而想必到这里大家都可以想到最简单朴实的 $Get,Marge$ 操作了.但是~

路径压缩与按秩合并*

倘若我们可以将每一个节点都直接指向代表,那该有多方便呀.
于是我们可以在每次 $Get$ 操作的同时,把每个访问过的点都直接指向树根,这种方法称之为路径压缩.使用该方法优化后的并查集,每次 $Get$ 的均摊复杂度为 $O(logN)$
而按秩合并在这里蒟蒻因为不太懂也就暂时不记录了，似乎用路径压缩已经够了.

当然, $code$ 是要有的.

struct Set{
    int fa[N] ;
    void init( ){
        for ( int i = 0 ; i <= n ; ++i ) fa[i] = i  ;//开始每个节点的代表元为自己
    }
    int get ( int x ){//Get操作
        if ( x == fa[x] )  return x ;//边界
        return fa[x] = get( fa[x] ) ;//路径压缩
    }   
    void marge ( int x , int y ){//合并
        fa[get(x)] = get(y) ;//代表元合并
    } 
}t;

这次我边写题边记录,我就信我是个唐人

连通性判断

$Topic:$

P1197 [JSOI2008] 星球大战

逆向思维,我们假设 $k$ 个点全被炸了,这个时候,图中就只有那些剩下的点,我们统计出这个时候的连通块个数,记为 $tot$ ,然后,我们倒序的将被炸掉的点加进图中,设这个点为 $u$ ,其连接的点为 $v_1,v_2,......,v_{cnt}$ , 我们顺序连接 $u$ 与 $v_i$ , 当 $v_i$ 在图中,则合并 $u$ 与 $v_i$ 点所在的集合(连通块),并更新 $tot$ 的值. 代码

---

P1783 海滩防御

把每个点抽象成一个平面上的点，它的坐标为 $(x_i,y_i)$ , 于是发现,若以两个点为圆心画圆,没有空隙的充要条件是 $2\ast r>=dis$ 其中 $dis$ 为两点的欧式距离.那么如果你认真审题,那么你一下就可以反应过来,要求 $r_{min}$ 使得点 $1$ 到 $m$ 连通(我们会把两个点相连).
怎么找呢?可以用二分,但是优美的是排序+并查集.具体的,我们先保存起每个点与其它全部点的距离.把这三个信息保存在结构体里.再建两个节点 $0$ 与 $m+1$ ,然后以每个点为起点, 向两个新建的节点分别连长度为$x_i\ast 2$ 以及 $(n-x_i)\ast 2$.再接着,以距离排序,由小到大遍历,并合并两个点,判断节点 $0$ 与 $m+1$ 是否连通.代码,记录.

非加权维护

扩展域并查集

普通并查集的局限性

普通并查集只能处理简单的连通性问题（如判断两个节点是否属于同一集合），但无法直接处理复杂关系：

1. 敌人的敌人是朋友（传递性）

2. 食物链中的捕食关系（环形关系）

3. 多类关系的矛盾检测（如同时是朋友和敌人）

此时，扩展域并查集通过“拆分元素”来解决这些问题。

扩展域的核心思想

每个元素拆分为多个逻辑域，表示不同的关系状态。

通过合并不同域来建立关系，通过查询域是否连通来判断关系是否合法。

举个经典荔子：敌人的敌人是朋友

假设元素 x 有两种状态：

• x_friend：表示 x 的朋友域
• x_enemy：表示 x 的敌人域

规则：

• 如果 x 和 y 是朋友：
  • 合并 x_friend 和 y_friend
  • 合并 x_enemy 和 y_enemy（敌人的敌人一致）
• 如果 x 和 y 是敌人：
  • 合并 x_friend 和 y_enemy
  • 合并 x_enemy 和 y_friend

---

• $例题$(蒟蒻可能没有习题)

P1525 [NOIP 2010 提高组] 关押罪犯

典型的扩展域,将点 $u+n$ 表示为 $u$ 的扩展域(点 $u$ 的反状态).
本提中因为只有两个集合,所以可以发现,自己敌人的敌人理应与自己在同一个集合.再由贪心,从愤怒值大的开始遍历,每次将 $u$ 连接 $v+n$ ,同时 $v$ 也连接 $u+n$ .再同时判断是否矛盾(两个点是否在同一个集合或者判断两点分别与自己的反状态是否在同一个集合)代码.

P2024 [NOI2001] 食物链

这次有了三个集合，那么依题意，我们给每个节点创造三个域，分别为同类域，天敌域，食物域.代码,记录.

带权并查集

带权并查集（Weighted Union-Find）是通过权值维护元素间关系的并查集变种，核心思想是在合并和查询过程中维护节点间的相对关系。它能够处理需要量化关系的复杂场景（如距离差、层级差等），典型应用包括食物链、差分约束、连通性带权判断等。 —DeepSeek-R1

核心思想

• 每个节点维护一个权值，表示该节点到父节点的某种关系（如距离、差值等）。
• 路径压缩和合并操作时动态更新权值，保持关系的正确性。

  ---

由于代码实现不是很模板,所以先来一道题.

P1196 [NOI2002] 银河英雄传说

这道题可以说是很经典了吧,我们可以用 $dis$ 数组表示节点 $i$ 到该集合代表元的距离.那么就会有以下两个核心代码

//fa[i]=i,size[i]=1,dis[i]=0
    int get ( int x ){
        if ( fa[x] == x ) return x ;
        int root = get ( fa[x] ) ;//递归计算
        dis[x] += dis[fa[x]] ;//边权求和
        fa[x] = root ;//路径压缩
        return fa[x] ;
    }

    void marge( int x , int y ){
//size[k]表示以k为代表的集合大小
        int rootx = get( x ) , rooty = get(y) ;
        fa[rootx] = rooty ;
        dis[rootx] = size[rooty] ;
        size[rooty] += size[rootx] ; 
    }

因为这道题的关系十分显然(简单相加),所以这里不给出解释.但是,要提的是我在刚学时的一个困惑.那就是如果多次 $get$ 操作, $dis$ 数组不是会一直累加吗(见下面的一行代码,可以看到 $di{s}_x$ 的值应该 会累加起来)?

dis[x] += dis[fa[x]] ;//边权求和

答案是否定的,因为别忘了 路径压缩!!!

代码

---

P5092 [USACO04OPEN] Cube Stacking

不想多说了(你猜为什么,你写一下就知道了).
代码,记录

---

来一个DeepSeek-R1的表格

带权 vs 扩展域

特性	带权并查集	扩展域并查集
核心思想	通过权值量化关系（如差值、模运算）	通过拆分多个逻辑域管理关系
空间复杂度	O(N)	O(K*N)（K为域数）
实现难度	需要推导权值公式，调试较复杂	逻辑直观，易于调试
适用场景	关系可量化（如模3、距离差）	关系种类明确且有限（如敌友）

---

到这里,并查集的基本内容算是结束了(对于本蒟蒻来说),如果以后做了些并查集的好题,我会在下面Update.