并查集

并查集概念

当我们在做题的时候，会有一些关于集合的操作，比如将两个集合合并，查询一个元素是否属于某个集合，判断两个元素是否属于同个集合等，并查集就是一种用于处理这些情况的数据结构，并 指集合合并， 查 指元素查询

既然有集合和元素关系判定的需求，那么首先我们得标识集合，比如说碗属于餐具，那么这里餐具就是这个集合的标识(名字)，在并查集中，集合有多种标识方法，最常见的一种是将代表元素作为集合表示，比如一个集合中包含了碗和盘子，那么我们可以随便选择一个，比如说碗，来标识集合

在具体实现中，并查集通过树形结构来实现，用根元素来标识集合，每个元素连向父节点，用于标识集合的根元素则连向自己

那么查找的时候只要沿着链寻找到根元素即可确定集合，查找的逻辑非常简单，沿着链往上查找，直到找到一个父节点连接指向自己的元素，，我们用c++简单地实现一下这个过程，这里用f数组表示父节点连接

// 查找 searchfather
int sf(int x){
    if (f[x] == x) return x; // 如果找到根元素则直接返回答案
    return sf(f[x]); // 否则返回 [继续往上找得到的答案]
}

在介绍并查集是如何实现集合合并之前，我们现在看一下并查集需要做哪些预处理

我们知道如果一个元素它的父节点连接如果指向自己，说明它用于标识这个集合 (当然用指向0，指向特殊值来标识都可以，上述例子是指向自己)，那么一开始每个元素都独立成为一个集合，就需要对每个元素自己构成的集合进行预处理————将父节点连接指向自己

用代码表示就是

// 预处理
for (int i = 1; i <= n; i++)
    f[i] = i;

而两个集合的合并，本质上就是，让代表两个集合的树结构成为一个树结构，并选出一个元素作为代表 (根元素)，那么我们发现一个最为简单的处理方法就是，将一棵树的根连向另一棵树的根，这样做就能满足所有的条件

如上图所示的两个集合，我们只要将5号节点的父节点连接指向1节点或者将1节点的父节点连接指向5节点即可完成合并

但是在正常情况下，都需要先找到集合的标识再对两个集合进行合并，需求一般长成这样

将3所在的集合和6所在的集合进行合并

这时候我们就需要先找到3所在的集合和6所在的集合，并对着两个集合的根元素做父节点连接操作，我们用C++代码简单地写一下这个过程

// 合并x所在的集合和y所在的集合
fx = sf(x); // 找到 x 所在集合
fy = sf(y); // 找到 y 所在集合
f[fx] = fy; // 将两者合并

当然熟练之后你可以把查找和合并写的更简洁

// 查找 三目表达式
int sf(int x){ return x == f[x] ? x : sf(f[x]); }
// 合并
f[sf(x)] = sf(y); 

查找路径优化

如果按照上述方法构建并查集并查找元素，会存在一个问题，如果不巧在合并的过程中形成了一条链，那么查找的复杂度会非常的高 (需要一路沿着父节点连接向上查找)，当然你可以说运气不好，但是一个优秀的算法必须要保证稳定的复杂度，在不同的测试数据情况下都表现良好

这里介绍两种常用的查找路径优化方式

路径压缩

最常用的一种查找路径优化方式是路径压缩，其基本思想是

在查找集合根元素的同时对查找经过的路径进行压缩

比如说，如果查找下图4节点所在集合的根元素，在查找过程中将4节点和3节点的父元素连接全都改为指向根节点，这样在下次查找的时候就不需要经过非常长的查找路径了

具体的实现非常的简单，就是在每个经过的节点处，将其父节点连接指向元素更改为，查询根元素返回的答案，这里用C++代码进行演示

int sf(int x){
    return f[x] == x ? x : f[x] = sf(f[x]); 
    // sf(f[x])返回的结果是集合的根元素
}

路径压缩后的查询均摊复杂度为$O(\alpha(n))$，这里$\alpha$指代反阿克曼函数

按秩合并

另一种常用的方式是按秩合并，通俗一点地说就是通过有序的集合合并方式，限制并查集树的高度

具体的实现思路就是，在合并的时候瞅瞅哪个集合树的高度是更高的，那么将其根元素作为合并后集合的根元素，因为高度小的集合并入高度大的集合，是不会增加高度的，只有两个高度相同的集合合并，才会使得高度增加

这里只要对于每个集合多维护一个参数h来表示高度(秩)即可，C++代码实现如下

void Union(int x, int y){
    int fx = sf(x);
    int fy = sf(y);
    // 保证fx的高度小于等于fy
    if (h[fx] > h[fy]) swap(fx, fy);
    // 合并
    f[fx] = fy;
    // 高度增加的情况
    if (h[fx] == h[fy]) h[fy]++;
}

并查集例题

亲戚

你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。

这个例题就是并查集的基础应用

• 信息处理

  A和B是亲戚：f[sf(A)]=sf(B)

• 询问处理

  A和B是否是亲戚：判断sf(A)是否等于sf(B)

• 注意点

  集合初始化

---

畅通工程

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

这个题涉及到并查集的一个常见的应用，连通分量计数，换句话说，就是统计有几个集合，因为距离全图连通还需要添加的边数就是集合的数量减一

统计集合的数量只需要计算做完集合合并之后，父节点连接指向自己的点 (f[i] == i) 的数目即可

---

团伙

在某城市里住着 n 个人，任何两个认识的人不是朋友就是敌人，而且满足：

1. 我朋友的朋友是我的朋友；
2. 我敌人的敌人是我的朋友；

所有是朋友的人组成一个团伙。告诉你关于这 n 个人的 m 条信息，即某两个人是朋友， 或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？ 

首先我们需要对题目的信息进行化简

朋友的朋友是朋友符合正常的集合合并逻辑，不需要特殊处理，敌人的敌人是朋友该如何处理是解决这个问题的关键

我们记x的敌人为enemy[x]，因为敌人的敌人是朋友，则A和B是敌人这个条件其实包含了两个信息：

1. enemy[A]和B是朋友
2. enemy[B]和A是朋友

所以这个题的处理逻辑就是，存储每个元素第一次出现的enemy，通过朋友的关系传递来标识集合

// 处理敌人关系
void EUnion(int a, int b){
    if (enemy[a]) Union(b, enemy[a]);
    else enemy[a] = b;
}
// 对于敌人关系需要处理两条信息
EUnion(A,B), EUnion(B,A)

---

巴士旅行

有n个城市，被m条边表示m条无向道路，每条边有一个时间，表示坐巴士从一个城市到另一城市需要等待的时间。Jack最多等待巴士x分钟，也就是说需要等待超过x分钟的巴士他就不会去坐，他在城市里可以得到休息，使得他恢复等待巴士的耐心。求有多少对城市(a,b), 他可以通过坐巴士的方式从a城市到达b城市。(a,b)和(b,a)算作不同的对

有多组询问，每组给出一个x，表示Jack最多等待的时间，求出在不同x条件下的答案

考虑单组询问，对于给定x，将所有边权不超过x的边的两端点所在的集合合并，最后每个集合对答案的贡献为

$size * (size - 1)$

考虑每次集合合并对答案造成的影响，假设将大小为 s1 的集合和大小为 s2 的集合进行合并，那么对答案的贡献为

$(s1 + s2) * (s1 + s2 - 1) - s1 * (s1 - 1) - s2 * (s2 - 1)$

即新产生的集合的贡献减去消失的集合贡献

我们可以记录每个询问原来位于询问列表中的位置，然后对询问根据x大小进行排序，对边按照权值大小进行排序，从小到大对边端点所在的两个集合进行合并处理，在处理完排序后询问列表对应的值之后将答案记录到对应的询问上

最后还原询问的顺序并输出即可

种类关系处理

为了说明什么是种类关系，我们先来看一个题

阵营

在某场战争中有两个敌对的阵营，周围城镇的士兵不是来自阵营A就是来自阵营B，现在告诉你一些士兵之间的关系，即他们来自同一个阵营或者来自不同的阵营，之后询问一些士兵之间的关系：来自同一阵营，来自敌对阵营，或者不确定 

这里有两个阵营，所以种类只有两种，非A即B，区别于上面的团伙一题

用并查集来处理种类关系通常有两种方法：加权和拆点 (处理种类关系的方法还有很多，暂且不讨论)

拆点

拆点，顾名思义，就是将一个点拆成多个点

以阵营一题为例，我们用两个点来表示一个士兵，一个点表示该士兵属于A阵营，另一个点表示该士兵属于B阵营

如果我们现在有两个士兵a和b，那么可以得到四个命题

1. a士兵属于A阵营
2. a士兵属于B阵营
3. b士兵属于A阵营
4. b士兵属于B阵营

如果得到信息 a士兵和b士兵属于同一阵营，那么1和3两个命题可以同时成立，2和4两个命题可以同时成立；如果得到的信息是 a士兵和b士兵属于不同阵营，那么1和4两个命题，2和3两个命题同时成立

我们将同时成立的命题归为一个集合，查询两个士兵关系的时候，对士兵对应的命题(两个点)的集合关系进行判断，就可以得到士兵之间的关系

在具体实现中，我们用点x表示x士兵属于A阵营，用点(x+n)表示x士兵属于B阵营

• 若给出信息：x和y属于同一阵营，则 Union(x ,y), Union(x+n, y+n)
• 若给出信息：x和y属于不同阵营，则 Union(x, y+n), Union(x+n, y)
• 若查询x和y的关系：
  • 若sf(x)==sf(y)||sf(x+n)==sf(y+n), 则为同一阵营
  • 若sf(x+n)==sf(y)||sf(x)==sf(y+n), 则为敌对阵营
  • 否则，关系未知

加权

加权的意思就是给边赋予权值，来表示并查集树上，点和父节点之间的关系，因为是树状结构，所以边信息可以直接记录在子节点上，而不需要额外对边进行处理

还是以阵营一题为例

假设我们在做并查集处理的时候在边上多记录一个信息，表示两点是敌对还是同阵营，那么在不做路径压缩的情况下，我们可以得到类似下图的结构

那么，通过计算路径上敌对边出现的次数，我们可以得到每个点和根元素之间的关系，如果两个点处在同一个集合中，我们又分别知道了这两个点和根元素的关系，那么这两个点的关系也可以轻易得到

那么压缩路径的情况下，无非是，更新路径上每个节点的父节点连接的同时，更新其向上连接的边属性(敌对/同阵营)，最终达到如下图所示的效果

我们用1表示敌对，0表示同阵营，那么点和集合根元素的关系即路径上经过的1数量对2取模得到的结果，也就是路径上的数字和对2取模

我们用r数组来表示点与父节点的关系，那么查找的代码可以这么写

int sf(int x){
    if (f[x] == x) return x;	
    int fx = sf(f[x]); // 保留父节点连接f[x]
    r[x] = (r[x] + r[f[x]]) % 2; // 此时，r[f[x]]为父节点和根元素的关系
    return f[x] = fx; // 更新父节点连接
}

而在两个集合合并的时候，我们需要先计算出两个节点和集合根节点之间的，然后用两个节点之间的关系去更新根节点之间的关系

void Union(int x, int y, int fx, int fy, int d){
    f[fy] = fx;
    r[fy] = (r[y] + r[x] + d) % 2; 
}

种类关系处理例题

食物链

食物链

草原上有三种物种，分别为A,B,C，A吃B，B吃C，C吃A。给定若干条信息，信息分为两种

1. 1 x y 表示x和y是同类
2. 2 x y 表示x吃y

问给出的信息有几条是和前面相违背的

这题同样可以用上述种类关系处理的两种方法来做

• 🌼 拆点
• 🌻 加权

将每个点拆点，比如x拆为，x-A，x-B，x-C 表示x属于A类，x属于B类，和x属于C类 (具体实现中用 x, x+n, x+2*n表示)

如果x和y属于同类，那么合并x-A和y-A，x-B和y-B，x-C和y-C

如果是x吃y的情况，那么合并x-A和y-B，x-B和y-C，x-C和y-A

对于条件矛盾判断:

如果给出信息是x和y属于同类，但是x和y+n或x和y+2n已经在同个集合中，那么该信息矛盾;

如果给出信息是x吃y，但是x和y或x和y+2n在同一个集合中，那么该信息矛盾

用边关系 0 表示x和y同类， 1 表示x吃y，2 表示x被y吃，则x和根结点的关系为其路径上经过的边权之和对3取余的结果，处理方式同阵营一题

带权并查集例题

在介绍种类关系处理的时候，我们已经介绍了加权方法，就是对每个节点附加信息，表示和父节点之间的关系，在压缩的时候同时进行加权信息的计算，除了种类关系表示之外，带权并查集还有更多的用途，这里用几个例题加以说明

龙珠

有标号为1到n的n个龙珠，分别放在对应标号为1到n的n个城市里。下面有两种操作:

1. T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中
2. Q A 表示查询A，需要知道A龙珠现在所在的城市，A所在的城市有几颗龙珠，A转移到这个城市移动了多少次，分别输出3个整数，表示上述信息。

我们来看每次询问需要输出的三个信息

1. A所在的城市
2. A所在的城市的龙珠数目
3. A龙珠到这个城市移动了几次

第一条信息用朴素的并查集就可以维护，第二条信息在两个集合合并的时候将集合大小相加即可 (记录在根元素)

而第三条信息的维护，需要在集合合并的时候加权给根元素连接的那条边，并在压缩时需要向下传递

我们可以发现每个龙珠从原来所在的城市移出仅会发生一次，所以每次移动，直接加权1即可，合并和路径压缩代码如下

// 路径压缩
int sf(int x){  
    if (f[x] == x) return x;  
    int fx = sf(f[x]); // 保留父节点连接f[x]
    move[x] += move[f[x]]; // 计算移动次数和
    return f[x] = fx;  // 更新父节点连接
}  
// 合并
void Union(int x,int y){  
    fx = sf(x); 
    fy = sf(y);  
    if(fx != fy){  
        f[fx] = fy;  
        count[fy] += count[fx]; // 龙珠数量统计
        move[fx] = 1; // 移动次数加权  
    }  
}  

试题判断

有n次询问，给出a到b区间的总和 (试题的区间分数)

如果一个“子区间和”与前面的“子区间和”冲突，即为错误（而且这个“子区间和”将在接下来的判断中被忽略）

问这n次给出的总和中有几次是和前面已经给出的是矛盾的

题目中给出了若干个区间和信息，我们先将其转化成点信息，区间和即前缀和的差，我们记$S_x$表示前x题的总分，那么a到b区间的和为c，就等价于式子 $S_b-S_a=c$

所以问题转化为给定若干个点之间的数值差，计算矛盾的次数，我们将数值差记录到边权上，压缩的同时计算数值差即可

核心代码

// 路径加权
int sf(int x) {
    if (x == f[x]) return f[x];
    int fx = sf(f[x]);
    sum[x] += sum[f[x]];
    return f[x] = fx;
}
void Union(int x, int y, int data) {
    int a = sf(x), b = sf(y);
    if (a == b) {
        if (sum[y] != sum[x] + data) ans++;
        return;
    }
    sum[b] = sum[x] + data - sum[y];
    f[b] = a;
} 

未完待续