【暑期每日一题】洛谷 P1551 亲戚

题目链接：P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：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

样例输入 #1

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出 #1

Yes
Yes
No

AC code:

#include<iostream>
#include<algorithm>

using namespace std;

int f[5010];

// 初始化 
void init(int n)
{
	for(int i=1;i<=n;i++)
		f[i]=i;
}

int getf(int v)
{
	if(f[v]==v)
		return v;
	else
	{
		f[v]=getf(f[v]);
		return f[v];
	}
}

void merge(int v,int u)
{
	int t1,t2;
	t1=getf(v);
	t2=getf(u);
	if(t1!=t2)
	{
		f[t2]=t1;
	}
}

int main()
{
	int sum=0;
	int n,m,p;
	cin>>n>>m>>p;
	init(n);
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	while(p--)
	{
		int x,y;
		cin>>x>>y;
		if(getf(x)==getf(y))
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	
	return 0;
}