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

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

什么是并查集？

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

0_1311901712oy9f.gif.jpg

并查集的优化:路径压缩

0_131190167189S8.gif.jpg

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

---

实现

#include <iostream>
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<length;i++){
        cout<<pre[i]<<"   ";
    }
    cout<<endl;
}

int main(){
    const int vertex=4;
    const int n=vertex+1;
    int pre[n];

    //初始化
    for(int i=1;i<n;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<n;i++){
        arr_root[i]=0;
    }

    //将是根节点的点置为1
    for(int i=1;i<n;i++){
        arr_root[find(pre,n,i)]=1;
    }

    //统计一下置为1的结点的个数
    int ans=0;
    for(int i=1;i<n;i++){
        if(arr_root[i]==1){
            ans++;
        }
    }

    cout<<ans<<endl;

    system("pause");
    return 0;
}

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

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

image.png