新get的数据结构——并查集

查并集是一个很重要的数据结构，特别适合解决一些类似于图，集合的问题。比如这个：http://acm.hdu.edu.cn/showproblem.php?pid=1232

什么是并查集？

为了解释并查集的原理，我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？
我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。
但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

0_1311901712oy9f.gif.jpg

并查集的优化:路径压缩

0_131190167189S8.gif.jpg

这样可以将查询一个结点的根节点的时间复杂度降到O(1)。

实现

#include
using namespace std;
//查找根节点
int find(int * pre,int length,int v){
int _v=v;
int root;
if(pre[_v]==_v){
return v;
}
while(pre[_v]!=_v){
_v=pre[_v];
}
root=_v;
//顺便完成路径压缩
_v=v;
while(pre[_v]!=_v){
int temp=pre[_v]; // 在改变上级之前用临时变量 j 记录下他的值
pre[_v]=root;//把上级改为根节点
_v=temp;
}
return root; //返回根节点 r
}
//判断v1 v2是否连通
//如果已经连通，就不用管了,如果不连通，就把它们所在的连通分支合并起,将v2合并到v1里面
void join(int * pre,int length,int v1,int v2){
int root_v1=find(pre,length,v1);
int root_v2=find(pre,length,v2);
if(root_v1==root_v2){
return ;
}else{
pre[v2]=root_v1;
}
}
void print(int * pre,int length){
for(int i=1;i cout< }
cout<}
int main(){
const int vertex=4;
const int n=vertex+1;
int pre[n];
//初始化
for(int i=1;i pre[i]=i;
}
print(pre,n);
join(pre,n,1,2);
join(pre,n,3,4);
print(pre,n);
//判断有几个根节点
int arr_root[n];
//初始化为0
for(int i=0;i arr_root[i]=0;
}
//将是根节点的点置为1
for(int i=1;i arr_root[find(pre,n,i)]=1;
}
//统计一下置为1的结点的个数
int ans=0;
for(int i=1;i if(arr_root[i]==1){
ans++;
}
}
cout< system("pause");
return 0;
}


关于数据结合和算法的其他文章：
这又是一个flag http://www.jianshu.com/p/1dc543da3897

update：
在论坛上面看见的一个问题，用并查的思想可以很快的算出来。

image.png