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）

 

转载于:https://www.cnblogs.com/CheeseZH/p/4554615.html

相关资源：数据结构—成绩单生成器