并查集，在一些有N个元素的集合套用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合併，其间要反覆查找一个元素在哪个集合中。这一类问题近几年来反覆出现在信息学的国际国内赛题中，其特点是看似并不複杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间複杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合併及查询问题。常常在使用中以森林来表示。
基本介绍
- 中文名：并查集
- 外文名：Union Find
- 用途：计算机编码
主要操作
初始化
把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间複杂度均为O(N)。
查找
查找元素所在的集合，即根节点。
合併
将两个元素所在的集合合併为一个集合。
通常来说，合併之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
例题
Description（题目描述）
若某个家族人员过于庞大，要判断两个是否是亲戚，确实不容易，给出某个亲戚关係图，求任意给出的两个人是否具有亲戚关係。
规定：x和y是亲戚，y和z是亲戚，那幺x和z也是亲戚。如果x,y是亲戚，那幺x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
Input（输入）
第一行：三个整数n,m,p，（n< =5000,m< =5000,p< =5000）
分别表示有n个人，m个亲戚关係，询问p对亲戚关係。
以下m行：每行两个数
，
，1< =，< =n，表示和具有亲戚关係。
接下来p行：每行两个数
，
，询问和是否具有亲戚关係。
Output（输出）
共P行，每行一个’Yes’或’No’。表示第个询问的答案为“有”或“没有”亲戚关係。
分析问题实质
初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。对于题目中的样例，以人为点，关係为边，建立无向图如下：
图0-0-1 {请补充图解}
比如判断3和4是否为亲戚时，我们检查3和4是否在同一个连通子图中，结果是在，于是他们是亲戚。又如7和10不在同一个连通子图中，所以他们不是亲戚。
用图的数据结构的最大问题是，我们无法存下多至(M=)2 000 000条边的图，后面关于算法时效等诸多问题就免谈了。
用图表示关係过于“奢侈”了。其实本题只是一个对分离集合（并查集）操作的问题。
例如样例：
9 7 1
2 4
5 7
1 3
8 9
1 2
5 6
2 3
1 9
我们可以给每个人建立一个集合，集合的元素值有他自己，表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关係a, b，则a和他的亲戚与b和他的亲戚就互为亲戚了，将a所在集合与b所在集合合併。对于样例数据的操作全过程如下：
初始状态：{1} {2} {3} {4} {5} {6} {7} {8} {9}
输入关係 分离集合
(2,4) {2,4}{1} {3} {5} {6} {7} {8} {9}
(5,7) {2,4} {5,7} {1} {3} {6} {8} {9}
(1,3) {1,3} {2,4} {5,7}{6} {8} {9}
(8,9) {1,3} {2,4} {5,7} {8,9}{6}
(1,2) {1,2,3,4} {5,7} {8,9}{6}
(5,6) {1,2,3,4} {5,6,7} {8,9}
(2,3) {1,2,3,4} {5,6,7} {8,9}
判断亲戚关係
(1,9)，因为1,9不在同一集合内，所以输出"NO"。
最后我们得到3个集合{1,2,3,4}、{5,6,7}、{8,9}，于是判断两个人是否亲戚的问题就变成判断两个数是否在同一个集合中的问题。如此一来，需要的数据结构就没有图结构那样庞大了。
算法需要以下几个子过程：
(1) 开始时，为每个人建立一个集合SUB-Make-Set(x)；
(2) 得到一个关係a b，合併相应集合SUB-Union(a,b)；
(3) 此外我们还需要判断两个人是否在同一个集合中，这就涉及到如何标识集合的问题。我们可以在每个集合中选一个代表标识集合，因此我们需要一个子过程给出每个集合的代表元SUB-Find-Set(a)。于是判断两个人是否在同一个集合中，即两个人是否为亲戚，等价于判断SUB-Find-Set(a)=SUB-Find-Set(b)。
有了以上子过程的支持，我们就有如下算法。
PROBLEM-Relations(N, M, a1,…,aM, b1,…,bM, Q, c1,…,cQ, d1,…,dQ)
for i←1 to N
do SUB-Make-Set(i)
for i←1 to M
do if SUB-Find-Set(ai) != SUB-Find-Set(bi)
then SUB-Union(ai, bi)
for i←1 to Q
do if SUB-Find-Set(ci)=SUB-Find-Set(di)
then output “Yes”
else output “No”
解决问题的关键便为选择合适的数据结构实现并查集的操作，使算法的实现效率最高。
注意事项
本题的输入数据量很大，这使得我们的程式会在输入中花去不少时间。如果你用Pascal写程式，可以用库函式SetTextBuf为输入档案设定缓冲区，这可以使输入过程加快不少。如果你是用C语言的话，就不必为此操心了，系统会自动分配缓冲区。
单鍊表实现
一个节点对应一个人，在同一个集合中的节点串成一条鍊表就得到了单鍊表的实现。在集合中我们以单鍊表的第一个节点作为集合的代表元。于是每个节点x（x也是人的编号）应包含这些信息：指向代表元即表首的指针head[x]，指向表尾的指针tail[x]，下一个节点的指针next[x]。
SUB-Make-Set(x)过程设计如下：
SUB-Make-Set(x)
10 head[x]←x
11 tail[x]←x
12 next[x]←NIL
求代表元的SUB-Find-Set(x)过程设计如下：
SUB-Find-Set(x)
13 return head[x]
前两个过程比较简单，SUB-Union(a,b)稍微複杂一点。我们要做的是将b所在鍊表加到a所在鍊表尾，然后b所在鍊表中的所有节点的代表元指针改指a所在鍊表的表首节点，如图所示。
图0-0-2
过程的伪代码如下：
SUB-Union(a,b)
14 next[tail[head[a]]]←head[b]
15 tail[head[a]]←tail[head[b]]
16 p←head[b]
17 while p != NIL
18 do head[p]←head[a]
19 p←next[p]
我们来分析一下算法的时间效率。SUB-Make-Set(x)和SUB-Find-Set(x)都只需要O(1)的时间，而SUB-Union(a,b)的时间效率与b所在鍊表的长度成线性关係。最坏情况下，即有操作序列SUB-Union(N-1,N), SUB-Union(N-2,N-1), …, SUB-Union(1,2)时，整个算法PROBLEM-Relations的时间複杂度为O(N+M+N^2+Q)=O(N^2+M+Q)。
由于算法的时间複杂度中O(M+Q)是必需的，因此我们要让算法更快，就要考虑如何使减小O(N^2)。
我们想到合併鍊表时，我们可以用一种启发式的方法：将较短的表合併到较长表上。为此每个节点中还需包含表的长度的信息。这比较容易实现，我们就不写出伪代码了。
时间複杂度。
首先我们给出一个固定对象x的代表元指针head[x]被更新次数的上界。由于每次x的代表元指针被更新时，x必然在较小的集合中，因此x的代表元指针被更新一次后，集合至少含2个元素。类似地，下一次更新后，集合至少含4个元素，继续下去，当x的代表元指针被更新 log k 次后，集合至少含k个元素，而集合最多含n个元素，所以x的代表元指针至多被更新 log n 次。所以M次SUB-Union(a,b)操作的时间複杂度为O(NlogN+M)。算法总的时间複杂度为O(NlogN+M+Q)。
并查集森林
并查集的另一种更快的实现是用有根树来表示集合：每棵树表示一个集合，树中的节点对应一个人。图示出了一个并查集森林。
图0-0-3
每个节点x包含这些信息：父节点指针p[x]，树的深度rank[x]。其中rank[x]将用于启发式合併过程。
于是建立集合过程的时间複杂度依然为O(1)。
SUB-Make-Set(x)
20 p[x]←x
21 rank[x]←0
用森林的数据结构来实现的最大好处就是降低SUB-Union(a,b)过程的时间複杂度。
SUB-Union(a,b)
22 SUB-Link(SUB-Find-Set(a),SUB-Find-Set(b))
SUB-Link(a,b)
23 p[a]←b
合併集合的工作只是将a所在树的根节点的父节点改为b所在树的根节点。这个操作只需O(1)的时间。而SUB-Union(a,b)的时间效率决定于SUB-Find-Set(x)的快慢。
SUB-Find-Set(x)
24 if x=p[x]
25 then return x
26 else return SUB-Find-Set(p[x])
这个过程的时效与树的深度成线性关係，因此其平均时间複杂度为O(logN)，但在最坏情况下（树退化成鍊表），时间複杂度为O(N)。于是PROBLEM-Relations最坏情况的时间複杂度为O(N(M+Q))。有必要对算法进行最佳化。
第一个最佳化是启发式合併。在最佳化单鍊表时，我们将较短的表链到较长的表尾，在这里我们可以用同样的方法，将深度较小的树指到深度较大的树的根上。这样可以防止树的退化，最坏情况不会出现。SUB-Find-Set(x)的时间複杂度为O(log N)，PROBLEM-Relations时间複杂度为O(N + logN (M+Q))。SUB-Link(a,b)作相应改动。
SUB-Link(a,b)
27 if rank[a]>rank
28 then p←a
29 else p[a]←b
30 if rank[a]=rank
31 then rank←rank+1
然而算法的耗时主要还是花在SUB-Find-Set(x)上。
第二个最佳化是路径压缩。它非常简单而有效。如图所示，在SUB-Find-Set(1)时，我们“顺便”将节点1, 2, 3的父节点全改为节点4，以后再调用SUB-Find-Set(1)时就只需O(1)的时间。
图0-0-4
于是SUB-Find-Set(x)的代码改为：
SUB-Find-Set(x)
32 if x≠p[x]
33 then p[x]←SUB-Find-Set(p[x])
34 return p[x]
该过程首先找到树的根，然后将路径上的所有节点的父节点改为这个根。实现时，递归的程式有许多栈的操作，改成非递归会更快些。
SUB-Find-Set(x)
35 r←x
36 while r≠p[r]
37 do r←p[r]
38 while x?r
39 do q←p[x]
40 p[x]←r
41 x←q
42 return r
改进后的算法时间複杂度的分析十分複杂，如果完整的写出来足可写一节，这里我们只给出结论：改进后的PROBLEM-Relations其时间複杂度为O(N+(M+Q)*A(M+Q,N))，其中A(M+Q,N)为Ackerman函式的增长极为缓慢的逆函式。你不必了解与Ackerman函式相关的内容，只需知道在任何可想像得到的并查集数据结构的套用中，A(M+Q,N)≤4，因此PROBLEM-Relations的时间複杂度可认为是线性的O(N+M+Q)。
最佳化路径压缩
思想
每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。
实现
第一步，找到根结点。
第二步，修改查找路径上的所有节点，将它们都指向根结点。
代码
#include<bits/stdc++.h>using namespace std;const int M = 1e3 + 10 ;int n , m ;int folk[M] ;int dsu (int u) { return u == folk[u] ? u : folk[u] = dsu (folk[u]) ;}int main () { int n ; scanf ("%d" , &n) ; for (int i = 0 ; i < n ; i ++) folk[i] = i ; scanf ("%d" , &m) ; while (m --) { int u , v ; scanf ("%d%d" , &u , &v) ; int _u = dsu (u) , _v = dsu (v) ; if (_u != _v) { folk[v] = _u ; } } for (int i = 0 ; i < n ; i ++) dsu (i) ; return 0 ;}图示
代码
Java版
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;public class Main{ private static int father[]; public static void main(String[]args)throws Exception{ StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); while(st.nextToken() != StreamTokenizer.TT_EOF){ int n=(int)st.nval; father=new int[n+1]; for(int i=1;i<=n;i++){ father[i]=i; } st.nextToken(); int m=(int)st.nval; st.nextToken(); int p=(int)st.nval; for(int i=0;i<m;i++){ st.nextToken(); int a=(int)st.nval; st.nextToken(); int b=(int)st.nval; union(a,b); } for(int i=0;i<p;i++){ st.nextToken(); int a=(int)st.nval; st.nextToken(); int b=(int)st.nval; a=findParent(a); b=findParent(b); System.out.println(a==b?"Yes":"No"); } } } private static void union(int f,int t){ int a=findParent(f); int b=findParent(t); if(a==b)return; if(a>b){ father[a]=b; } else { father[b]=a; } } private static int findParent(int f){ while(father[f]!=f){ f=father[f]; } return f; }}C++版
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>using namespace std;int fa[50002],a,b,m,n,p;/*x代表例题中的人，fa[x]中所存的数代表这一集合中所有人都与一个人有亲戚关係相当于例题中第一个集合所有的元素都与第一个元素有亲戚关係搜寻时只要找元素所指向的fa[x]=x的元素(即父元素)然后比较两个元素的父元素是否相同就可以判断其关係*/void build(int qwq) {for(int i=1;i<=qwq;i++) fa[i]=i;return ;}//初始化，一开始每个点单独成集合 int find(const int &x) {return fa[x]==x?x:fa[x]=find(fa[x]);}//找到x的最远祖先，并且压缩路径bool che(const int &x,const int &y){return find(x)==find(y);}//判断x,y是不是在同一个集合里，直接判断最远祖先是不是一样的 void mer(const int &x,const int &y) {if(!che(x,y)) fa[fa[x]]=fa[y];return ;}//合併x,y，我们在判断x和y是不是同一个集合里，路径压缩之后fa[x],fa[y]已经是最远祖先了，所以直接将fa[x]的父亲连线起来就好 int main(){ int i; scanf("%d%d%d",&n,&m,&p); build(n); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b), mer(a,b); } for(i=1;i<=p;i++) { scanf("%d%d",&a,&b); if(che(a,b)) printf("Yes\n"); else printf("No\n"); } return 0;}Pascal版
var father:array[1..5000] of longint; i,j,k,p,n,m:longint; function getfather(v:longint):longint;//寻找根节点begin if father[v]=v then exit(v); father[v]:=getfather(father[v]); exit(father[v]);end;procedure merge(x,y:longint);//合併两集合var xx,yy:longint;begin xx:=getfather(x); yy:=getfather(y); father[xx]:=yy;end;function judge(x,y:longint):boolean;//判断是否在一集合中var xx,yy:longint;begin xx:=getfather(x); yy:=getfather(y); exit(xx=yy);end;begin readln(n,m,p); for i:=1 to n do father[i]:=i; for i:=1 to m do begin readln(j,k); merge(j,k); end; for i:=1 to p do begin readln(j,k); if judge(j,k) then writeln('Yes') else writeln('No'); end;end.