P1551 亲戚(并查集)

题目背景

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

题目描述

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y的亲戚，y 的亲戚也都是 x 的亲戚。

输入格式

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

以下 m 行：每行两个数 Mi​，Mj​， N1≤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

 并查集的基本应用

#include <iostream>
#include <vector>
 
using namespace std;
 
constexpr int N=5005;
 
int f[N];
vector<int>g[N];
 
void unite(int x,int y){
    x=f[x],y=f[y];
    if(x==y) return;
    if(g[x].size()>g[y].size()) swap(x,y);
    while(!g[x].empty()){
        f[g[x].back()]=y;
        g[y].push_back(g[x].back());
        g[x].pop_back();
    }
}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        f[i]=i;
        g[i].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        unite(u,v);
    }
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(f[u]==f[v])
            printf("Yes\n");
        else
            printf("No\n");
    }
}