1、 简述
并查集（Disjoint set或是Union-find set）是一种树形的算法设计，常见于解决一些不交叉结合（Disjoint Sets）的合拼及查看难题。
2、 操作过程
并查集是一种比较简单的算法设计，它关键涉及到2个操作过程，各自为：
A． 合拼2个不交叉结合
B． 分辨2个原素是不是归属于同一个结合
（1） 合拼2个不交叉结合（Union(x,y)）
合拼实际操作非常简单：先设定一个二维数组Father[x]，表明x的“爸爸”的序号。那麼，合拼2个不交叉结合的方式便是，寻找在其中一个结合最爸爸的爸爸（也就是最悠久的先祖），将此外一个结合的最悠久的先祖的爸爸偏向它。
图中为2个不交叉结合，b图为合拼后Father(b):=Father(g)
（2） 分辨2个原素是不是归属于同一结合（Find_Set(x)）
本实际操作可变换为找寻2个原素的最悠久先祖是不是同样。能够选用递归完成。
3、 提升
（1） Find_Set(x)时，途径缩小
找寻先祖时，大家一般选用递归搜索，可是当原素许多 亦或是整棵树变成一条链时，每一次Find_Set(x)全是O(n)的复杂性。为了更好地防止这类状况，大家需对途径开展缩小，即在我们历经”递推”寻找先祖连接点后，”回朔”的情况下顺带将它的子孙后代连接点都立即偏向先祖，那样之后再度Find_Set(x)时复杂性就变为O(1)了，如下图所显示。由此可见，途径缩小便捷了之后的搜索。
（2） Union(x,y)时，按秩合拼
即合拼的情况下将原素少的结合合拼到原素多的结合中，那样合拼以后树的高宽比会相对性较小。
4、 程序编写完成
int father[MAX]; /* father[x]表明x的父节点 */
int rank[MAX]; /* rank[x]表明x的秩 */
/* 复位结合 */
void Make_Set(int x)
{
father[x] = x; //父节点给自己（依据具体情况特定父节点可转变）
rank[x] = 0; //秩为0（依据具体情况复位秩还可以有一定的转变）
}
/* 搜索x原素所属的结合,回朔时缩小途径 */
int Find_Set(int x)
{
if (x != father[x])
{
rank[father[x]] = rank[x];
//递归，以寻找最悠久先祖
//回朔时缩小途径：途径上的全部子孙后代连接点都偏向最悠久先祖
father[x] = Find_Set(father[x]);
}
return father[x];
}
/*
按秩合拼x和y所属的结合
下边的那一个if else构造并不是肯定的，实际依据状况转变
可是，服务宗旨是不会改变的即，按秩合拼，自动更新秩。
*/
void Union(int x, int y)
{
x = Find_Set(x); //寻找最悠久先祖
y = Find_Set(y);
if (x == y) return; //2个原素归属于同一个结合
if (rank[x] > rank[y]) //把深层小的结合合拼到深层大的结合中去
{
father[y] = x;
rank[x] = rank[y]; //升级合拼后的深层
}
else
{
if (rank[x] == rank[y])
{
rank[y] ;
}
father[x] = y;
}
}
5、 复杂性剖析
空间复杂度为O(N)，创建一个结合的算法复杂度为O(1)，N次合拼M搜索的算法复杂度为O(M Alpha(N))，这儿Alpha是Ackerman涵数的某一反函数，在非常大的范畴内（人们现阶段观察到的宇宙空间范畴估计有10的80三次方个分子，这低于前边常说的范畴）这一涵数的值能够当做是不超4的，因此并查集的实际操作能够当作是线形的。实际复杂性剖析全过程见参考文献（3）。
6、 运用
并查集常做为另一种繁杂的算法设计或是优化算法的存储结构。普遍的运用有：求无向图的连通分量数量，近期公共性先祖（LCA），带限定的工作排列，完成Kruskar优化算法求最小生成树等。
7、 参考文献
（1） 并查集：http://www.nocow.cn/index.php/并查集
（2） 博闻《并查集详解》：http://www.cnblogs.com/cherish_yimi/
（3） Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524.
