本文共 1192 字，大约阅读时间需要 3 分钟。

描述

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

格式

输入格式

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

输出格式

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

样例1

样例输入1

6 5 31 21 53 45 21 31 42 35 6

样例输出1

YesYesNo

限制

各点1S

#include 
   
    #include 
    
     #define MAX 5001 using namespace std; // father[x]表示x的父节点int father[MAX]; // 初始化集合void Make_Set(int x){
   	father[x] = x;} // 查找x元素所在的集合,回溯时压缩路径int Find_Set(int x){
   	if (x != father[x])	{
   		father[x] = Find_Set(father[x]);	}	return father[x];} // 合并x,y所在的集合void Union(int x, int y){
   	x = Find_Set(x);	y = Find_Set(y);	if (x == y)	{
   		return;	}	else	{
   		father[y] = x;	}} int main(){
   	int n, m, p;	int x, y;	cin >> n >> m >> p; 	// 初始化 	for (int i = 1; i <= n; i++)	{
   		Make_Set(i);	} 	//读入亲戚关系 	for (int i = 1; i <= m; i++)	{
   		cin >> x >> y;		Union(x, y);	} 	//询问亲戚关系 	while (p--)	{
   		cin >> x >> y;		if (Find_Set(x) == Find_Set(y))		{
   			cout << "Yes" << endl;		}		else		{
   			cout << "No" << endl;		}	} 	system("pause");	return 0;}
    
   

转载地址：https://blog.csdn.net/bodhiye/article/details/70846552 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！