题目描述

我看题解只有一个，还是c++的就想写一个c语言的
如果对并查集这个理念还不懂的小伙伴可以看看这个
https://blog.csdn.net/qq_41593380/article/details/81146850
这个用将故事的方式吧并查集讲的很好我也是从这里开始
理解并查集的。
这题我用的是并查集的路径压缩希望对你们写题有所帮助

C 代码

#include <stdio.h>
#define N 20010
int n,m,q,a,b;
int f[N];

int find(int k)         //路径压缩
{
    if(f[k]==k) return k;       //如果他的老大是他自己就返回这个数
    else return f[k]=find(f[k]);    //这是路径压缩的精髓，就是说当前我指向的
    //老大如果不是真正意义上的老大，那我就递归找到真正的老大并指向它
}

int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for(i=0;i<=n;i++) f[i]=i;   //初始化每个人的老大都是他自己
    while(m--)  
    {
        scanf("%d%d",&a,&b);
        f[find(a)]=find(b); //让a的老大，当b的老大的小弟
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&a,&b);
        if(find(b) == find(a)) printf("Yes\n"); //如果他们是同一个老大就输出Yes
        else printf("No\n");        //反之No
    }
    return 0;
}