比赛 数据结构应用练习2 评测结果 AAAAAAAAAAAA
题目名称 亲戚 最终得分 100
用户昵称 ┭┮﹏┭┮ 运行时间 0.069 s
代码语言 C++ 内存使用 0.98 MiB
提交时间 2023-07-28 16:05:13
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;
const int N = 20010;
int n,m,q;
int pre[N],de[N];
//  父亲  树的深度 
int fa(int x){
    if(x == pre[x])return x;
    return pre[x] = fa(pre[x]);
}//路径压缩,如果不压缩有可能变为一条链,改为菊花图 
void jia(int x,int y){
    int fx = fa(x);
    int fy = fa(y);
    if(fx != fy){
        if(de[fx] > de[fy]){
            pre[fy] = fx;
        }
        else{
            if(de[fx] == de[fy])de[fy]++;//如果深度相等,则必须要多1深度 
            pre[fx] = fy;
        }//根据深度大小,将深度小的连到深度较大的 
    }
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        pre[i] = i;
        de[i] = 1;
    }
}//输入 
void work(){
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        jia(x,y);//x与y连一起 
    }
}
int main(){
    freopen("relations.in","r",stdin);
    freopen("relations.out","w",stdout);
    init();//输入 
    work();//把所有亲戚连一起 
    scanf("%d",&q);
    for(int i = 1;i <= q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(fa(x) == fa(y))printf("Yes\n");
        else printf("No\n");//如果有同一个祖先则Yes,反之则No 
    }
    
    return 0;
    
}