洛谷 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​，1≤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<bits/stdc++.h> using namespace std; int n,m,p; const int N=5010; int fa[N]; int find(int x) { if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } int main() { cin>>n>>m>>p; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int m1,m2; cin>>m1>>m2; int fa1=find(m1); int fa2=find(m2); fa[fa1]=fa2; } for(int i=1;i<=p;i++) { int p1,p2; cin>>p1>>p2; if(find(p1)==find(p2)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }