并查集

并查集维护一张无向图，支持以下两种操作：

1.连接两个点

2.查询一个点所在的连通块

并查集的两种优化方式：

路径压缩：$O(\alpha (n))$

按秩合并：$O(\log n)$

Part 1：图的连通性

图的遍历也可以求图的连通性，但其复杂度为$O(n)$，如果要多次修改并查询，复杂度无法承受。

例题1：[JSOI2008][luogu1197][FAIOJ102]星球大战

两种操作，删点，求全图连通块个数。

并查集只支持连边，不支持删边。所以 时 光 倒 流

这样删点就变成加点了。每加一个点都把它和已经存在的点的边连上即可。

复杂度$O(m\alpha (n))$

例题2：[Corn#3][FAIOJ11012]邪恶入侵

$R$越大，由原点可到达的点就越多。

因此将每两点之间的距离排序，再将询问的$R$排序，双指针遍历两个数组即可。

合并的同时要维护连通块的大小。

复杂度$O((n^2+q)\log n)$

例题3：[Corn#2][FAIOJ11007]幽香的宴会

与上题类似，将询问按$P_i$排序，将边按边权排序，双指针遍历。

当加边的时候，要维护两个连通块的前$k$大点权。

我们直接在每个连通块的祖先处都维护一个堆，当两个连通块合并的时候，把小块中的元素依次插入大块的堆中即可。

当堆中元素达到$k$个时，每次加入新元素时都将最小的元素弹出。

因为入堆的操作不会超过$O(n\log n)$次，所以总复杂度为$O(n{\log }^{2}n+q\log q)$

Part 2：拆点建图

“拆点”是图论中非常常见的方法。

当一个点有多种状态时，我们一般考虑把它的每种状态都视为一个点。

拆点在并查集、最短路、强连通等多种问题中都有很多应用。

例题4：[FAIOJ1342]团伙

本题模型是一道最“原始”的并查集问题。但除了有两个点在同一集合的关系外，还有两个点不在同一集合的关系。

我们将一个人$u$拆成两个点$u$和$u^{\prime }$。表示$u$的“身份”是0或1。连通的0和连通的1是朋友，连通的0和1是敌人。

若$u,v$是朋友，则$u$和$v$连边，$u^{\prime }$和$v^{\prime }$连边；

若$u,v$是敌人，则$u^{\prime }$和$v$连边，$u$和$v^{\prime }$连边。

连边就表示两者或者同时成立，或者同时不成立

这样题目中的两个限制即可全部体现。

当统计团伙个数时，只需统计连通块数量即可。注意：全是反集中点的连通块不要统计。

复杂度$O(m\alpha (n))$

本题可以用搜索代替并查集。但事实上并查集更好写，而且复杂度差不多。

例题5：[NOI2015][luogu1955][FAIOJ13150]程序自动分析

先把所有=都用并查集合并。

再判断有没有≠在同一集合内的即可。

复杂度$O(n\log n)$（这个$\log$是因为要离散化编号）

例题6：[NOIP2010][luogu1525][FAIOJ10102]关押罪犯

又是经典的“最大值最小”问题。二分答案。

问题转化为：冲突超过$x$的罪犯不能关押在同一牢房，问是否有合法方案。

剩下的就和例题4一样了。

复杂度$O(m\alpha (n)\log C)$

例题7：[NOI2001][luogu2024]食物链

类似于上面几道题的思路，把每个动物$u$拆成三个点$A_u,B_u,C_u$。

如果$x$和$y$是同类，则有$(A_x,A_y),(B_x,B_y),(C_x,C_y)$连边；

如果$x$吃$y$，则有$(A_x,B_y),(B_x,C_y),(C_x,A_y)$连边。

如果连边时发现同一个动物的两个点将要连通，则说明这句话是假话。

复杂度$O(m\alpha (n))$。

Part 3：带权并查集

带权并查集在维护连通块的同时，还维护每个节点与连通块祖先的距离。

例题8：[NOI2002][luogu1196][FAIOJ103]银河英雄传说

本题要求支持两个操作：

合并两个队列，具体操作是把一个队列整体接到另一个队列后面；

查询一个队列中的两个点之间的距离。

我们维护一个$dis$数组，$di{s}_i$表示点$i$到所在队的队首的距离。

当把$i$为队首的队列接到$j$为队首的队列末尾时，$di{s}_i+=s{z}_j$；

另外路径压缩时也要更新$dis$值。

复杂度还是$O(m\alpha (n))$。