算法学习--并查集相关知识及例题

一、并查集的定义

二、基本操作

1、初始化

一开始，每个元素都是独立的集合

#include<iostream>

using namespace  std;

const int maxN=1000;
int father[maxN];


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

    return 0;
}

2、查找

递推版本：

//返回元素x所在的根节点
int findFather(int x)
{
    while(x!=father[x])
    {
        x=father[x];
    }
    return x;
}

递归版本：

//返回元素x所在的根节点
int findFather(int x)
{
    if(x==father[x])return x;
    else return findFather(father[x]);
}

3、合并

void Union(int a,int b)
{
    int fatherA= findFather(a);//找到根节点
    int fatherB= findFather(b);
    if(fatherA!=fatherB)//说明不是同一个集合
    {
        father[fatherA]=fatherB;
    }
}

4、记录树高防止退化

三、路径压缩

递推写法：

int findFather(int x)
{
   int a=x;
   while(x!=father[x])
   {
       x=father[x];//找到x是根节点
   }
   while(a!=father[a])
   {
       int z=a;
       a=father[a];
       father[z]=x;//对每一个结点，都把其父节点设为x
   }
   return x;
}

递归写法：

int findFather(int x)
{
    if(x==father[x])return x;
    else{
        int F= findFather(father[x]);
        father[x]=F;
        return F;
    }
}

四、例题

1、好朋友

#include<iostream>

using namespace  std;

const int maxN=110;
int father[maxN];
bool isRoot[maxN];
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        isRoot[i]=false;
    }
}
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;
    }
    return x;
}
void Union(int a,int b)
{
    int fa= findFather(a);
    int fb= findFather(b);
    if(fa!=fb)
    {
        father[fa]=fb;
    }
}
int main()
{
   int n,m;
   while(scanf("%d%d",&n,&m)!=EOF)
   {
       init(n);
       int a,b;
       for(int i=0;i<m;i++)
       {
           scanf("%d%d",&a,&b);
           Union(a,b);
       }
       for(int i=1;i<=n;i++)
       {
           isRoot[findFather(i)]=true;
       }
       int ans=0;
       for(int i=1;i<=n;i++)
       {
           ans+=isRoot[i];
       }
       printf("%d\n",ans);
   }
    return 0;
}

4 2
1 4
2 3

2

7 5
1 2
2 3
3 1
1 4
5 6

3

2、食物链