快速搞定并查集算法

c/c++

浏览数:97

2019-8-9


算法介绍

wiki

并查集

通俗解释

零基础学并查集算法

算法实现(C语言)

  • Find函数(未采用路径压缩)
int Find(int x)
{
    int r = x;
    while(pre[r] != r)
    {
        r = pre[r];
    }
    return r;
}
  • Find函数(路径压缩递归实现)
int Find(int x)
{
    if(pre[x] == x) return x;
    else
    {
        pre[x] = Find(pre[x]);
        return pre[x];  
    } 
}
  • Find函数(路径压缩非递归实现)
int Find(int x)
{
    int r = x;
    while(pre[r] != r)
    {
        r = pre[r];
        int i = x,int j;
        while(i != r)
        {
            j = pre[i];
            pre[i] = r;
            i = j;
        }
    }
    return r;
}
  • Join函数
void Join(int x,int y)
{
    int fx = Find(x),fy = Find(y);
    if(fx != fy) pre[fx] = fy;
}

算法实战

  • HOJ-1232
    修改的地方是每相连两个城镇需要额外多一步 —— 减少道路数。
#include<stdio.h>
int pre[1000];
int Find(int x)
{
    int r = x;
    while(pre[r] != r)
    {
        r = pre[r];
        int i = x,int j;
        while(i != r)
        {
            j = pre[i];
            pre[i] = r;
            i = j;
        }
    }
    return r;
}
int Join(int x,int y,int roadNum)
{
    int fx = Find(x),fy = Find(y);
    if(fx != fy) 
    {
        pre[fx] = fy;
        return roadNum-1;
    }
    else return roadNum;
}
void Init(int n)
{
    for(int i = 1;i <= n;i++)
    {
        pre[i] = i;
    }
}
int main()
{
    int N,M,ret = 0,i,a,b;
    while(scanf("%d",&N)&&N)
    {
        Init(N);
        ret = N-1;
        scanf("%d",&M);
        for(i = 0;i < M;i++)
        {
            scanf("%d %d",&a,&b);
            ret = Join(a,b,ret);
        }
        printf("%d\n",ret);
    }
    return 0;   
} 

作者:闽A2436