并查集(Union-find Sets):
先说一下这几天研究并查集的感悟吧!以前学习并查集感觉没什么不就是一个查询+合并吗? 开始几道题也很简单很快水之,谁知到后面遇到深层次的就不是如何是好。顿时感觉并查集好强大。
定义:并查集是一种树型的数据结构,树中的每一个节点代表一个元素,用于处理一些不相交集合的合并与查询问题。应用:求无向图的连通分量个数、最小公共祖先、带限制的作业排序、Kruskal 算法求最小生树.
三种基本操作:
1) 初始化: init ( n ) 建立一个有n个元素的并查集,使每一个元素指向自身
.
代码:
const int MX =100006 ; struct node { int parent,relation ; }T[MX] ; void init(int n) { for(int i=1 ;i<=n ;i++) { T[i].parent=i ; T[i].relation=0 ;// 表示此节点与根节点的关系,如果只是单纯的并查集这里可以省略 } }
2) 查找 : find( x ) 查找 x 的祖先.(这样可以判断两个元素是否在同一个集合中)
代码:
int find(int x) { return T[x].parent==x ? x : T[x].parent=find(T[x].parent) ;// 路径压缩 }
3)合并 :union_find( x , y ) 合并 x 与 y 所在的集合.
代码:
void union_find(int x,int y) { int ax=find(x) ; int ay=find(y) ;// 寻找根节点 if(ax!=ay) T[ax].parent=ay ; }
并查集优化:
1) 按秩合并(启发式合并):这种方法按照两个树的高度合并,将高度小的合并到高度大的上。
代码:
void union_find(int x,int y) { int ax=find(x) ; int ay=find(y) ;// 寻找根节点 if(ax!=ay) { if(T[ax].rank<T[ay].rank)// 比较树的高度 T[ax].parent=ay ; else { T[ay].parent=ax ; if(T[ax].rank==T[ay].rank) T[ax].rank++ ; } } }
2)按集合中元素的个数合并:将两个集合合并时将元素少的集合合并到元素多的集合上,可以不用定义一个数组来表示个数,直接用T[x].parent 来表示,开始将其初始化为 -1 ,这样如果T[x].parent 为负数代表是根节点,-T[x].parent 就表示所在集合元素个数。
void union_find(int x,int y) { int ax=find(x) ; int ay=find(y) ;// 寻找根节点 if(ax!=ay) { if(T[ax].parent<T[ay].parent)// 比较节点多少 { T[ax].parent+=T[ay].parent ; T[ay].parent=ax ; } else { T[ay].parent+=T[ax].parent ; T[ax].parent=ay ; } } }