并查集

2017-04-05  本文已影响0人  Mapoos

用途

主要用于解决判断两结点是否能连通之类的问题。
  
思想

建立并查集数组set[],初始化全部置-1。set[b]=a代表结点b的父结点为a。判断两结点是否连通,只要依次找到两结点的根结点并判断是否相同即可。若不同,将一结点的根节点连接作为另一节点根节点的子树,即可完成连通操作。

/*寻根*/
int findRoot(int x)
{
    while(set[x]!=-1)
        x=set[x];
    return x;
}

/*连通操作*/
void Union(int a,int b)
{
    set[findRoot(b)]=findRoot(a);
}

注意

  用以上方法操作时,一旦数据过多,往往会造成运行超时的结果,原因在于并查集树过高,搜索根节点时间长。下面提供两种解决思路:
  
1.路径压缩
  变更set[i]值的含义,将set[i]直接指向包含结点i的树的根节点,使每次查找根节点所需时间大大减少。具体做法为:每一次寻根的时候,变更set[i]值为根节点。经过路径压缩后效率可以达到O(N)。

/*路径压缩*/
int findRoot(int x)
{
    /*注意x即为根节点的情况,此时直接返回x即可*/
    if(set[x]==-1)
        return x;
    else
    {
        int temp=x;     //先将x的值保存下来
        while(set[x]!=-1)
            x=set[x];
        set[temp]=x;    //更新set[]
        return x;
    }
}

2.按秩归并
  压缩路径存在的一个问题是会破坏树的形状,这是可以考虑使用按秩归并的方法。
  对于两颗高度不一的树,若将高树并到矮树上,则得到的树高度为原高树高度加一,为了不使树一直增高,我们采取的做法是每一次合并都将矮树合并到高树上(通过根节点的值来记录树高,即set[root]=-树高)。当然也可以从树的规模入手,将小树归并到大树上。
  最坏情况下树高O(logN),按秩归并的复杂度可以低至O(NlogN)。

/*比高度,set[root]存储高度*/
void Union(int a,int b)
{
    int aRoot=findRoot(a);
    int bRoot=findRoot(b);
    if(set[aRoot]<set[bRoot])       //若a为高树
        set[bRoot]=aRoot;
    else        
    {
        if(set[aRoot]==set[bRoot])  //若树高相等
            --set[bRoot];    //合并后树高要加一
        set[aRoot]=bRoot;
    }
}
/*比规模,set[root]存储规模*/
void Union(int a,int b)
{
    int aRoot=findRoot(a);
    int bRoot=findRoot(b);
    if(set[aRoot]<set[bRoot])   //a规模大于b
    {
        set[aRoot]+=set[bRoot];//注意规模要合并
        set[bRoot]=aRoot;
    }
    else
    {
        set[bRoot]+=set[aRoot];
        set[aRoot]=bRoot;
    }
}

3.以上两种方法相结合,可以实现-1s,非常暴力。

上一篇 下一篇

猜你喜欢

热点阅读