关于亲戚的近10条评论(全部评论)
烦，真的烦真的好烦 2021-07-09 16:57 44楼
啊啊啊 szy 2021-07-09 16:33 43楼
Yes和No只有首字母大写...提交N次... 冷月星云 2019-07-08 16:20 42楼
真棒写了好几遍忘了输入输出（/笑哭）弟弟 2019-07-04 09:04 41楼
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int pre[20000+10]={0}; int find(int x) { int r=x; while(pre[r]!=r) r=pre[r]; return r; } int main() { freopen("relations.in","r",stdin); freopen("relations.out","w",stdout); int n,m; cin>>n>>m; //int rank[pre+10]; int a,b; for(int i=1;i<=n;++i) pre[i]=i; for(int i=1;i<=m;++i) { scanf("%d%d",&a,&b); pre[b]=pre[a]; int x=find(a),y=find(b); if(x!=y){ pre[a]=pre[b]; } } for(int i=1;i<=n;i++) pre[i]=find(pre[i]); int q; cin>>q; for(int i=1;i<=q;++i){ scanf("%d%d",&a,&b); if(pre[a]==pre[b]){ cout<<"Yes"<<endl; //cout<<pre[a]<<" "<<pre[b]<<endl; } else{ cout<<"No"<<endl; } } return 0; } 贺越云 2018-11-10 10:13 40楼
上榜1榜2榜3的都是运气好（经实证） 1233 2018-10-10 22:27 39楼
并查集首题留念~ ShallowDream雨梨 2018-09-03 19:40 38楼
就是个裸的并查集 Handwer 2018-07-19 11:33 37楼
为什么第九个点电脑和评测的结果不同 qwq 东林桂香 2017-05-28 22:03 36楼
初次接触并查集。。。小字、小瓶子 2017-05-04 20:11 35楼

259. 亲戚

★ 输入文件：relations.in 输出文件：relations.out 简单对比
时间限制：1 s 内存限制：128 MiB

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手是计算机。

为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，Grant和Tension是亲戚等，从这些信息中，你可以推出xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

第一行包含两个整数$n,m$，表示有$n$个人和$m$个关系，这些人的编号为$1,2,\cdots,n$。

接下来$m$行，每行两个整数$x, y$，说明$x$和$y$是亲戚。

接下来一行一个整数$q$，表明有$q$个询问。

接下来$q$行，每行两个整数$c,d$，表示询问$c$和$d$是否为亲戚。

输出共$q$行，对于每个询问，若$c$和$d$为亲戚，则输出Yes，否则输出No。

Yes
No
Yes

对于测试点$1\sim 5$，$n\leq 1000, 1\leq q\leq 10$。

对于测试点$6\sim 10$，$q\leq 10$。

对于测试点$11\sim 12$，$n\leq 2\times 10^4,m\leq 10^5,q\leq 10^5$。