比赛 |
数据结构应用练习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;
}