3024: 【普及-】【P1551】亲戚
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：4
题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定： 和 是亲戚， 和 是亲戚，那么 和 也是亲戚。如果 ， 是亲戚，那么 的亲戚都是 的亲戚， 的亲戚也都是 的亲戚。
输入
第一行：三个整数 ，（），分别表示有 个人， 个亲戚关系，询问 对亲戚关系。
以下 行：每行两个数 ，，，表示 和 具有亲戚关系。
接下来 行：每行两个数 ，询问 和 是否具有亲戚关系。
输出
行，每行一个
Yes 或 No。表示第 个询问的答案为“具有”或“不具有”亲戚关系。样例输入 复制
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6样例输出 复制
Yes
Yes
No提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010
int n,m,p,x,y,fa[MAXN];
int find(int x){
if (fa[x]==x) return x;
return fa[x]=find(fa[x]);
/*非递归方法
while(fa[x]!=x) {
x=fa[x];
}
return x;
*/
}
void join(int c1,int c2) {
int f1=find(c1),f2=find(c2);
if (f1!=f2) fa[f2]=f1;
}
int main(){
cin>>n>>m>>p;
for (int i=1;i<=n;i++) fa[i]=i; //初始化
for (int i=1;i<=m;i++) { // 合并亲属关系
cin>>x>>y;
join(x,y);
}
// 根据代表是否相同，查询亲属关系
for (int i=1;i<=p;i++) {
cin>>x>>y;
if (find(x)==find(y))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010
int n,m,p,x,y,fa[MAXN],size[MAXN];
//一定不要忘了初始化，每个元素单独属于一个集合
void init() {
memset(size,1,sizeof(size));
for(int i=1;i<=n;i++) {
fa[i]=i;
}
}
int find(int x){
//查询集合的“代表”
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
//顺便【路径压缩】
}
void join(int c1,int c2){
//合并两个集合//f1为c1的代表，f2为c2的代表
int f1=find(c1),f2=find(c2);
if(f1!=f2) {
if(size[f1]<size[f2]) //【取较大者】作为代表
swap(f1,f2);
fa[f2]=f1;
size[f1]+=size[f2];//只有“代表”的size是有效的
}
}
int main(){
cin>>n>>m>>p;
init(); //初始化
for (int i=1;i<=m;i++) { // 合并亲属关系
cin>>x>>y;
join(x,y);
}
// 根据代表是否相同，查询亲属关系
for (int i=1;i<=p;i++) {
cin>>x>>y;
if (find(x)==find(y))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}