亲戚(洛谷)---简单并查集

待我称王封你为后i 2023-07-09 06:27 14阅读 0赞

## 题目描述 ##

题目背景  
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述  
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入格式  
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

输出格式  
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例  
输入 \#1 复制  
6 5 3  
1 2  
1 5  
3 4  
5 2  
1 3  
1 4  
2 3  
5 6  
输出 \#1 复制  
Yes  
Yes  
No  
说明/提示  
非常简单的并查集入门题哦！！！

## 简单说下这题的写法 ##

这题直接套并查集的模板就好了，对于这题我是加了路径压缩和按秩合并来写的，起初我以为并查集会出现重复的枝条，后来我发现并不是。  
这道题目的话就是先套并查集的模板，然后一个循环m次，判断x和y的父节点是否一样，一样的话就Y不一样的话就N。  
代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<limits>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define ll long long
    int fa[5005];
    int Rank[5005];
    int Find(int x)
    {
        
        return fa[x]==x?x:(fa[x]=Find(fa[x]));
    }
    void Merge(int i,int j)
    {
        
        int x,y;
        x=Find(i),y=Find(j);
        if(Rank[x]<=Rank[y])
            fa[x]=y;
        else
            fa[y]=x;
        if(Rank[x]==Rank[y]&&x!=y)
            Rank[y]++;
    }
    int main()
    {
        
        int n,m,p;
        cin>>n>>m>>p;
        for(int i=1;i<=n;i++)
            {
        
                fa[i]=i;
                Rank[i]=1;
            }
        for(int i=1;i<=m;i++)
        {
        
            int x,y;
            cin>>x>>y;
            Merge(x,y);
        }
        for(int i=1;i<=p;i++)
        {
        
            int x,y;
            cin>>x>>y;
            x=Find(x),y=Find(y);
            if(x==y) cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        return 0;
    }