专题：并查集

· · 个人记录

1.初始化：元素独立成一个集合，即自己是自己的代表

int fa[SIZE];
for(int i=1;i<=n;i++)fa[i]=i;

2.查找：查询元素所在集合的代表

本质：就是找父亲的父亲的父亲...,直到代表，即到自己的父亲就是自己时

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

如果链太长，多次查找长链，效率太低，继续进行路径压缩，每次执行查询操作时，把访问过的每个点都直接接到代表下面，那么当这条被压缩后，下次再查询的时候就能很快访问到自己的总代表（树根）。

//路径压缩，将路径上每个点直接接到树根
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

3.合并：将两个元素所在集合合并在一起

void merge(int x,int y)
{
    fa[find(y)]=find(x);
    //将y所在集合的代表，改为x所在集合的代表
}

一种是根据集合大小，将小集合并入大集合里面；

一种是根据树的深度，将深度小的并入深度大集合中；

//初始化同时出示siz数组
//按照集合siz合并
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;

void merge(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y)return ;  //同一个集合不能再合并，否则siz错误

    if(siz[x]<siz[y])swap(x,y);

   fa[y]=x;
   siz[x]+=siz[y];
}

//按照树的深度合并

for(int i=1;i<=n;i++)fa[i]=i,dep[i]=1;

void merge(int x,int y)
{
  x=find(x);y=find(y);
  if(x==y)return ;

  if(dep[x]<dep[y])swap(x,y);

    fa[y]=x;
    dep[x]=max(dep[x],dep[y]+1);
}

启发式合并是数据结构中一种重要的思想，应用广泛，不局限于并查集中。启发式合并基本原则是：把“小的结构”合并到“大的结构”中，只增加“小的结构”的查询代价。把所有结构全部合并起来，增加的总代价不会超过 NlogN， 故单独采用“启发式合并”优化的并查集，每次find的均摊复杂度为O(logN)。

在算法竞赛的实际代码中，即便不使用启发式合并，代码也往往能够在规定时间内完成任务。在 Tarjan 的论文中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是O(m\log_{}n)。在姚期智的论文中，证明了不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 O(m\alpha(m,n))。

如果只使用启发式合并，而不使用路径压缩，时间复杂度为 O(m \log n)。由于路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可撤销并查集、可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集。

经典题目

例1：P1955 程序自动分析

题意：

给定n个约束变量之间关系的条件：相等（x_i=x_j）或者不等(x_i\ne x_j).判定是否可以分别为每一个变量赋予一个适当的值，使得上述约束条件都满足。

1\leq n \leq 10^5,1 \leq x \leq 10^9

【分析】

相等的关系可以看作无向图中的一条边，变量相等当且仅当它们连通，可以把变量分成若干个结合，每个集合都对应无向图中的一个连通块。

第一种方法，在无向图上执行深度优先遍历，划分出图中每个连通块。

第二种方法，使用并查集动态维护。一开始，各个变量单独成一个集合；然后处理相等约束，将两个集合合并；最后处理“不等”约束条件，如果存在不等的两个变量处于同一个集合，那么肯定无法满足。

值得注意的是，本题x范围很大（会爆空间），需要使用离散化，将x映射到1-2n之内。

参考代码：点击

例2：UVA1316 Supermarket

题意：

给定n个商品，每个商品利润p_i过期时间d_i,每天只能卖一个商品，过期商品不能卖，如果安排销售顺序，使得收益最大，求最大收益。

1 \leq N,p_i,d_i \leq 10^4

【分析】

第一种贪心策略，建立一个按照利润建立一个小根堆，按照过期时间从小到大排序，先销售早过期的商品，也就是丢入到堆中，堆中的商品就是要销售的，如果堆的size小于当前商品的过期时间，当前商品直接入堆；如果堆的size，替换丢堆顶的商品，也就是堆顶商品出堆后，当前商品入堆。最后，堆中商品价值总和即为答案。

参考代码：点击

第二种贪心策略，优先销售利润大的商品，并且对每个商品，应该尽量在它过期之前而且是最晚的时间卖出-占用较晚时间，显然对其他商品具有“决策包容性”。

如果之间利用数组占位，复杂度太高，可以利用并查集优化，查找每个“位置”往前数第一个空闲的位置（包括它本身），当一个位置被占用，就把该“位置”在并查集中指向它前一个“位置”。 按照商品利润从大到小排序，并建立一个关于“天数”的并查集，起初每一天各自构成一个集合，对于每个商品，d天之后过期，就在并查集中查询d的树根（记为r）。若r大于0，则安排该商品在第r天卖出，合并r与r-1（令r为r-1的子节点），答案累加该商品的利润。

参考代码：点击

拓展1：

“带边权”并查集

并查集实际上是有若干棵树构成的森林，可以在树上每条边记录一个权值，即维护一个数组d,用d[x]保存节点x到父亲节点fa[x]之间的边权。路径压缩后，每个访问过的节点都会指向数根，如果我们同时更新这些节点d值，就可以利用路径压缩过程来统计每个节点到数根之间的路径上的一些信息。

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

题意： 有一个划分成N列的星际战场，各列依次编号为1,2，...,N。有N艘战舰，也依次编号为1,2，...,N,其中第i号战舰处于第i列。

有M条指令：

$C,i,j$,表示询问第$i$号战舰与第$j$号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。 $ N \leq 30000,M \leq 5*10^5

【分析】 让树上每条边带权值为1，树上两点之间的距离减1就是二者之间间隔的战舰数量。

带权路径压缩

int fa[N],d[N],size[N],n;
int find(int x)
{
    if(fa[x]==x)return x;
    int r=find(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=r;
}
void merge(int x,int y)
{
    x=find(x);y=find(y);
    fa[y]=x;
    d[y]=size[x];
    size[x]+=size[y];
}

完整代码：点击

例题4：P5937 Parity game

本题是经典好题

可以转化为带权并查集，也可以用扩展域并查集实现。

参考代码：点击

拓展2：

“扩展域”并查集

扩展域并查集，也叫“种类并查集”：普通并查集维护的是具有联通性、传递性的关系，例如亲戚的亲戚还是亲戚，有时也需要维护敌人的敌人是朋友，就可以使用种类并查集。

当遇到A和B是敌人关系怎么处理? 我们可以利用虚拟节点，建立起敌人关系，A与B是敌人关系，若B+n与B是敌人关系，那么B+n与A就是朋友关系。也就是当遇到敌人关系时，A与B是敌人关系，转为A与B+n是朋友关系，B与A+n是朋友关系。 本质上维护的是循环对称关系。

例题5：P1525 关押罪犯

【分析】 第一种方法，二分

如果保留超过最小怨气值越大的边，那么最小怨气值越小，保留的边越多，当保留的边中，出现奇数条边构成的环（简称奇环），无论如何也无法分配罪犯到两个监狱（一所监狱内罪犯之间没有连边），实际这种情况就是图不是二分图。也就是说，最小怨气值越大，保留的边越少，越容易构成二分图，也就是存在单调性，可以二分最小怨气值。

参考代码：点击

第二种方法，种类并查集

其实很容易想到，这里可以贪心，把所有矛盾关系从大到小排个序，然后尽可能地把矛盾大的犯人关到不同的监狱里，直到不能这么做为止。这看上去可以用并查集维护，但是有一个问题：我们得到的信息，不是哪些人应该在相同的监狱，而是哪些人应该在不同的监狱。这怎么处理呢？

可以利用“扩展域”并查集进行转换。A和B在不同监狱，那么A与B+n就在同一个监狱（合并），B和A+n也在一所监狱（合并）。当新来一条边，这条边的两顶点已经在同一个集合中，此时说明两人在同一监狱，那就会产生怨气，此时边权就是最小怨气值。

参考代码：点击

例6： 食物链

根据题意：A->B->C->A(A吃B,B吃C,C吃A)，会构成这种循环敌对关系，可以使用扩展域并查集，A的食物记为A+n,A的天敌记为A+2n，那么当出现一个关系A->B(A吃B),那就可以等价于(B,A+n)是同类，(B+n,A+2n)是同类，（A,B+2n）是同类，同类具有传递性（而吃与被吃不具备传递性），所以就可以转化并查集维护这种关系。当输入关系出现矛盾，那就是假话。

参考代码：点击

例7：UVA11987 Almost Union-Find

有 n 个集合，m 次操作。规定第 i 个集合里初始只有 i。有三种操作：

  1. 输入两个元素 p 和 q，若 p 和 q 不在一个集合中，合并两个元素的集合。
  2. 输入两个元素 p 和 q，若 p 和 q 不在一个集合中，把 p 添加到 q 所在的集合。
  3. 输入一个元素 p，查询 p 所在集合的元素个数和所有元素之和。

分析： 将一个集合中的元素，添加到另外一个集合中，如果使用普通的并查集，这个元素的儿子要处理，比较麻烦。

添加虚拟根节点，使得每一个节点没有儿子，移动单点就容易多了，i的父亲为虚拟节点n+i，虚拟节点n+i的父亲节点为它本身n+i,查找合并操作并不影响,i节点下面没有儿子节点，利于单点移动。

参考代码：点击