并查集

Dear 丶 2021-11-11 08:04 372阅读 0赞

**例题：**  
![输入样例][20190805122001677.png]  
输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判断后面输入的电脑编号是否连接；当输入‘I’时，把后面输入的电脑编号连接；当输入是‘S’时，停止输入结束，输出这n台电脑是否形成网络；  
**主函数**

int main()
    { 
        int s[100];
        int n;
        char a;
        scanf("%d",&n);
        for(i=0;i<n;i++) //初始化；
            s[i]=-1;
        while(~scanf("%c",&a)&&a!='S')
        { 
            if(a=='I')
                input(s);
            else if(a=='C')
                check(s);
            else
                judge(s,n);
        }
        return 0;
    }

**把某两个元素连接起来**

void input(int s[])
    { 
        int u,v;
        scanf("%d %d",&u,&v);
        int r1=find1(s,u-1);
        int r2=find1(s,v-1);
        if(r1!=r2)
        { 
            guibing(s,r1,r2);
        }
    }

**查找某个元素属于哪个并查集**

1、正常查询

int find1(int s[],int k)
    { 
        while(s[k]>=0)
        { 
            k=s[k];
        }
        return k;
    }

2、压缩路径查询

int find2(int s[],int k)//实现了路径压缩；
    { 
        if(s[k]<0)
            return x;
        else
            return s[x]=find2(s,s[k]);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]  
**把两个元素所在的并查集归并成一个并查集**

1、普通归并

void guibing(int s[],int r1,int r2)
    { 
        s[r1]=r2;
    }

2、桉树高归并

void anzhiguibing1(int s[],int r1,int r2)//桉树高进行归并
    { 
        if(s[r1]<s[r2])
        { 
            s[r2]=r1;
        }
        else if(s[r1]<s[r2])
        { 
            s[r1]=r2;
        }
        else
        { 
            s[r2]=r1;
            s[r1]--;
        }
    }

3、按规模归并

void anzhiguibing2(int s[],int r1,int r2)//按规模归并
    { 
        if(s[r2]<s[r1])
        { 
            s[r2]=s[r2]+s[r1];
            s[r1]=r2;
        }
        else
        { 
            s[r1]=s[r2]+s[r1];
            s[r2]=r1;
        }
    }

**判断两个元素之间是否已连接**

void check(int s[])
    { 
        int u,v;
        scanf("%d %d",&u,&v);
        int r1,r2;
        r1=find1(s,u-1);
        r2=find1(s,v-1);
        if(r1==r2)
            printf("yes\n");
        else
            printf("no\n");
    }

**判断整个系统是否已合并为一个并查集**

void judge(int s[],int n)
    { 
        int i;
        int count=0;
        for(i=0;i<n;i++)
        { 
            if(s[i]==-1)
                count++;
        }
        if(count==1)
            printf("The network is connected.\n");
        else
            printf("There are %d components.\n",count);
    }

[20190805122001677.png]: /images/20211109/bf20c4a7af0a4aa9886a41ae1f52fe4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]: /images/20211109/4ce76dd45291446ea2e94c0b8e6ae6a0.png