定义: 在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题.
用于处理一些不相交集合S={S1, S2, …,Sn},每个集合Si都有一个特殊元素root[Si],称为集合的代表元.
并查集的一个重要的应用是确定给定集合上的等价关系的个数。
等价关系是一个具有自反、对称和传递三个性质的关系。
等号“=”在实数集合R上是一个等价关系。
对于实数中的任意x、y、z。一定满足下列关系：
1）、x=x （自反性）
2）、如果x=y，则y=x （对称性）
3）、如果x=y，y=z，则x=z （传递性）
自反性：令C={（x,y）|x、y属于A}，设D是C的某非空子集，如果（x，y）属于D，则称x，y有（由D规定的）关系，记为x ~ y。
如果（x，x）属于D总成立，则称那个由D规定的关系具有自反性。
例子：x，y都属于实数集。那么上述的C可视为（平面直角坐标系下的）实二维空间，令D为y=x这条直线，即{（x,y）|x=y}。实际上D规定的就是两个实数“相等”这个关系，即任何（x，y）属于D意味着x=y。易验证，此关系具自反性，因为（x,x）总属于D。
并查集支持以下三种操作:
1、Make_Set(x) 把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身。
2、Find_Set(x) 查找一个元素所在的集合
查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。
判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图
3、Union(x,y) 合并x,y所在的两个集合
合并两个不相交集合操作很简单：
利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。如图
实现方法
1.用编号最小的元素标记所在集合；
2.定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合；
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
set[i] |
1 |
2 |
1 |
4 |
2 |
6 |
1 |
6 |
2 |
2 |
不相交集合：{1,3,7}, {4}, {2,5,9,10}, {6,8}
并查集的优化
1、Find_Set(x)时 路径压缩
寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度。路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了。
朴素查找的代码,适合数据量不大的情况：
int findx(int x)
{
int r=x;
while(parent[r] !=r)
r=parent[r];
return r;
}
下面是采用路径压缩的方法查找元素：
int find(int x) //查找x元素所在的集合,回溯时压缩路径
{
if (x != parent[x])
{
parent[x] = find(parent[x]); //回溯时的压缩路径
} //从x结点搜索到祖先结点所经过的结点都指向该祖先结点 return parent[x];
}
上面是一采用递归的方式压缩路径， 但是，递归压缩路径可能会造成溢出栈，下面我们说一下非递归方式进行的路径压缩：
int find(int x)
{
int k, j, r;
r = x;
while(r != parent[r]) //查找跟节点
r = parent[r]; //找到跟节点，用r记录下
k = x;
while(k !=r) //非递归路径压缩操作
{
j = parent[k]; //用j暂存parent[k]的父节点
parent[k] = r; //parent[x]指向跟节点
k = j; //k移到父节点
}
return r; //返回根节点的值
}
2、Union(x,y)时 按秩合并
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。
为了实现一个按秩合并的不想交集合森林，要记录下秩的变化。对于每个结点x，有一个整数rank[x]，它是x的高度（从x到其某一个后代叶结点的最长路径上边的数目）的一个上界。（即树高）。当由MAKE-SET创建了一个单元集时，对应的树中结点的初始秩为0，每个FIND-SET操作不改变任何秩。当对两棵树应用UNION时，有两种情况，具体取决于根是否有相等的秩。当两个秩不相等时，我们使具有高秩的根成为具有较低秩的根的父结点，但秩本身保持不变。当两个秩相同时，任选一个根作为父结点，并增加其秩的值路径压缩。
简单代码解释：
1 void Union(int a, int b)
2 {
3 if(village[a].weight == village[b].weight) {//树高一样
4 village[b].parent = a;
5 village[a].weight += 1;
6 }
7 else if (village[a].weight > village[b].weight) {//矮树并入高树
8 village[b].parent = a;//并入a
9 }
10 else { village[a].parent = b;//并入b
11 }
12 }
function MakeSet(x)
x.parent := x
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
xRoot.parent := yRoot
n个元素的m次不相交集合操作n个元素的m次不相交集合操作n个元素的m次不相交集合操作n个元素的m次不相交集合操作Code并查集的时间复杂度
n个元素的m次不相交集合操作
按秩合并：时间：O(m*lg(n))
路径压缩：最坏:O（n+lg(n)）
例题
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
主要代码
13 #include<iostream>
14 using namespace std;
15
16 int pre[1050];
17 bool t[1050]; //t 用于标记独立块的根结点
18
19 int Find(int x)
20 {
21 int r=x;
22 while(r!=pre[r])
23 r=pre[r];
24
25 int i=x,j;
26 while(pre[i]!=r)
27 {
28 j=pre[i];
29 pre[i]=r;
30 i=j;
31 }
32 return r;
33 }
34
35 void mix(int x,int y)
36 {
37 int fx=Find(x),fy=Find(y);
38 if(fx!=fy)
39 {
40 pre[fy]=fx;
41 }
42 }
43
44 int main()
45 {
46 int N,M,a,b,i,j,ans;
47 while(scanf("%d%d",&N,&M)&&N)
48 {
49 for(i=1;i<=N;i++) //初始化
50 pre[i]=i;
51
52 for(i=1;i<=M;i++) //吸收并整理数据
53 {
54 scanf("%d%d",&a,&b);
55 mix(a,b);
56 }
57
58
59 memset(t,0,sizeof(t));
60 for(i=1;i<=N;i++) //标记根结点
61 {
62 t[Find(i)]=1;
63 }
64 for(ans=0,i=1;i<=N;i++)
65 if(t[i])
66 ans++;
67
68 printf("%d ",ans-1);
69
70 }
71 return 0;
72 }//dellaserss