数据结构之并查集小结
<div id="cnblogs_post_body">数据结构---并查集小结By-Missa
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。 （百度百科）
大体分为三个：普通的并查集，带种类的并查集，扩展的并查集（主要是必须指定合并时的父子关系，或者统计一些数据，比如此集合内的元素数目。）
<div class="cnblogs_code" >http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gifhttp://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gifView Code <div id="cnblogs_code_open_355b78b9-4551-4621-969d-583c9074fab6" class="cnblogs_code_hide"> 1 #define MAXN 100005 2 int n,m,k,fa; 3 int rank; 4 void init(int n)//初始化 5 { 6 for(int i=0;i<=n;i++) 7 { 8 fa=i; 9 rank=0;10 }11 }12 //查找的时候，进行路径压缩fa=find(fa)13 //把查找路径上的结点都指向根结点，减少树的高度。14 int find(int x)15 {16 if(x != fa)17 fa=find(fa);//路径压缩18 return fa;19 }20 //合并21 void unio(int x,int y)22 {23 int fx=find(x),fy=find(y);24 if(fx==fy) return ;25 if(rank<rank)//将rank值小的合并到大的中26 fa=fx;27 else28 {29 fa=fy;30 if(rank==rank)31 rank++;32 }33 }34 //或（忽略按秩合并，懒的时候经常这么敲.....时间上也不知道会差多少，没有试过。。）：35 void unio(int x,int y)36 {37 int fx=find(x),fy=find(y);38 if(fx==fy) return ;39 fa=fx;40 }
页:
[1]