并查集

扫码查看

在学习krustra的算法时遇到了一个查找是否存在环路的算法,代码如下:

 int find(int *parent,int f)
 {
     while(parent[f]>0)
     {

     f=parent[f];
     }

         return f;
 }
 for(int i=0;i<k;i++)
         {
             int temp=0;
             int a,b;
             a=find(parent,Edge[i].begin);
             b=find(parent,Edge[i].end);
             if(a!=b)//无环
             {

                 parent[a]=b;
                 sum+=Edge[i].weight;
                 temp++;
              } 

“被酒莫惊春睡重,赌书消得泼茶香,当时只道是寻常。”初见时仅仅是将它作为一个简单的递归转迭代的算法来看待,但之后再刷题时一而再再而三的遇上它,并且为它红了樱桃,却没能绿了芭蕉,经过查询方识卿之芳名------并查集:
是一种维护集合的数据结构,并查集三字分别取自:"Union","FInd",""Set'',初始化:

for(int i=1;i<=N;i++)
{
father[i]=i;
}

FIND:

int findfather(int x)
{
while(father[x]!=x)
{
x=father[x];
}
return x;
}

Union:

void Union(int a,int b)
{
 int m=findfather(a);
 int n=findfather(b);
 if(m!=n)
{
   father[m]=n;
}//反之,若相等则证明成环;
}
}

当然上述的算法时没有经过优化的,当元素成一条链式,一次向父节点进行查找会导致计算量过大,因而需要在find上做些手脚,即每一次查找完后,都让查找完的所有结点都指向统一的父节点,这样同一个集合中的查找就会缩短很多的时间:
Find:

int findfather(int x)
{
int a=x;
while(x!=father[x])
{
    x=father[x];
}
while(a!=father[a])
{
int z=a;
a=father[a];
father[z]=x;//将原先的根节点改为x;
}
}

这就是所谓的并查集算法;

举一道例题:
蓝桥杯和根植物:

问题描述
  w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
  这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。


  如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入格式
  第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
  接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
  接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。


  格子的编号一行一行,从上到下,从左到右编号。
  比如:5 * 4 的小格子,编号:
  1 2 3 4
  5 6 7 8
  9 10 11 12
  13 14 15 16
  17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
这道题的实质即为求连通子集的个数,并查集AC;
AC代码:
#include<iostream>
#include<string.h>
using namespace std;
int par[1000005];
int cnt;
int n,m;
int circle;
int count;
void init()
{
    for(int i=1;i<=cnt;i++)
    {
        par[i]=i;
    }

}
int Find(int x)
{
    int i=x;
    while(par[i]!=i)
    {
        i=par[i];
    }
    int r=x;
    while(par[r]!=r)
    {
        int z=r;
        r=par[r];
        par[z]=i;
    }
    return i;
}
void Union(int a,int b)
{
    int m=Find(a);
    int n=Find(b);
    if(m!=n)
    {
        par[m]=n;
    }
    else
    {
        circle++;
    }
}
int main()
{
    int u,v;
    cin>>m>>n;
    cnt=m*n;

    int k;
    cin>>k;
    init();
    for(int i=1;i<=k;i++)
    {
        cin>>u>>v;
        Union(u,v);
    }
    for(int i=1;i<=cnt;i++)
    {
        if(par[i]==i) count++;
    }
    cout<<count<<endl;
    //cout<<circle<<endl;//多次一举,多输入个环的个数;

}

 

12-14 17:55
查看更多