1、介绍
并查集是一种树型数据结构，用于处理一些不相交集合的合并问题。
并查集主要操作有：
（1）合并两个不相交集合；
（2）判断两个元素是否属于同一个集合；
（3）路径压缩；
2、常用操作
用father[i]表示元素i的父亲结点，例如：
用某个元素所在树的根节点表示该元素所在集合；
判断两个元素是否属于同一个集合的时候，只需要判断他们所在树的根节点是否一样即可；
也就是说，当我们合并两个集合的时候，只需要在两个根节点之间连边即可。
获取根节点代码：
1 int findFather(int x){ 2 if(father[x] == x) 3 return x; 4 else 5 return findFather(father[x]); 6 }
判断是否属于同一集合代码：
1 bool judge(int x,int y){ 2 int fx,fy; 3 fx = findFather(x); 4 fy = findFather(y); 5 return fx==fy; 6 }
合并不同元素到同一集合代码：
1 void unionSet(int x,int y){ 2 x = findFather(x); 3 y = findFather(y); 4 father[x] = y; 5 }
3、优化1——路径压缩
思想
每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快；
步骤
（1）找到根节点；
（2）修改查找路径上的所有结点，将他们都指向根节点；
例如查找下面并查集中的“20”，“9，10，20”均在查找路径上，则进行路径压缩
带路径压缩的查找算法代码
1 int findFather(int x){ 2 int r = x; 3 //get the root of x 4 while(father[r] != r) 5 r = father[r]; 6 int i=x; 7 //update the nodes in searching path 8 while(i != r){ 9 j = father[i]; 10 father[i] = r; 11 i = j; 12 } 13 return r; 14 }
4、优化2-合并
思想
两个集合合并，也就是2棵树合并，为了降低合并后的树的深度，一般采取将深度小的树的树根作为深度大的树的树根的孩子节点。
策略
增加辅助空间记录树的深度。
合并代码：
1 void unionSet(int x,int y){ 2 x = findFather(x); 3 y = findFather(y); 4 if(x == y) 5 return ; 6 if(rank[x] > rank[y]){ 7 father[y] = x; 8 }else{ 9 if(rank[x] == rank[y]) 10 rank[y]++; 11 father[x] = y; 12 } 13 }
5、并查集例题
5.1、HDOJ1232（畅通工程）
http://www.cnblogs.com/CheeseZH/archive/2012/05/13/2498073.html
5.2、HDOJ1272（小希的迷宫）
http://www.cnblogs.com/CheeseZH/archive/2012/05/25/2518639.html
6、并查集练习题
（1）银河英雄传说（NOI2002）
（2）食物链（NOI2001）
（3）Parity（ceoi99）
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/4554615.html，如需转载请自行联系原作者
