vijos 1034 家族(水题日常)
2024-09-28 20:25:03
描述
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
规定: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 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
样例输出1
Yes
Yes
No
限制
各点1S
来源
cdwind整理提交
#include <cstdio> int n,m,p,fa[];
int find_fa(int x)
{
return x==fa[x]?x:fa[x]=find_fa(fa[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=;i<=n;i++) fa[i]=i;
for(int x,y;m--;)
{
scanf("%d%d",&x,&y);
int fx=find_fa(x),fy=find_fa(y);
if(fx!=fy) fa[fy]=fx;
}
for(int x,y;p--;)
{
scanf("%d%d",&x,&y);
if(find_fa(x)==find_fa(y)) printf("Yes\n");
else printf("No\n");
}
return ;
}
最新文章
- Python的平凡之路(12)
- .net该的帐
- Sunglasses
- 在ASP.NET中实现压缩多个文件为.zip文件,实现批量下载功能 (转载并优化处理篇)
- 利用mongodb开发lbs应用实践【转】
- .net source code
- 2015 UESTC Winter Training #6【Regionals 2010 >;>; North America - Rocky Mountain】
- Qt 域名转成IP
- 通过 C# 代码操作 Google 日历
- eclipse 配置scala问题-More than one scala library found in the build path
- [翻译] 编写高性能 .NET 代码--第五章 通用编码与对象设计 -- 类 vs 结构体
- python之反射和内置函数__str__、__repr__
- C语言运算符优先级总结
- 关于NGUI Shader 和 Draw Call的优化 &; 模糊shader
- kubernetes 学习资料
- centos7.2 +cloudstack 4.11 +KVM +ceph 安装配置(网卡带聚合)
- [kx]宇宙-银河
- 断开的管道 java.io.IOException: Broken pipe 解决方法
- Session 活化与钝化 与tomcat钝化驱动器
- Apache 虚拟目录和默认首页的设置