Vijos 1034题:家族
发布日期:2021-09-23 21:27:28 浏览次数:0 分类:技术文章

本文共 1404 字,大约阅读时间需要 4 分钟。

描述

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

格式

输入格式

第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Ai和Bi具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。

输出格式

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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Vijos 1036题:安装服务器
下一篇:Vijos 1007题:绕钉子的长绳子

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.172.111.71]2022年05月22日 10时11分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章