CODEVS 1073 家族
2024-09-10 08:40:53
题目描述 Description
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
输入描述 Input Description
第一行:三个整数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是否具有亲戚关系。
输出描述 Output Description
P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
样例输入 Sample Input
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
样例输出 Sample Output
Yes
Yes
No
数据范围及提示 Data Size & Hint
n<=5000,m<=5000,p<=5000
解题思路
真心不知道谁给这个题定了一个大师级,明明就是一个水到不能再水的并查集练习,懒得解释,直接上代码。‘
program family;
var
f:Array[..] of longint;
n,m,p,i,a,b:longint;
function root(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=root(f[x]);
exit(f[x]);
end; begin
read(n,m,p);
for i:= to n do f[i]:=i;
for i:= to m do
begin
read(a,b);
if root(a)<>root(b) then
f[root(a)]:=root(b);
end; for i:= to p do
begin
read(a,b);
if root(a)=root(b) then writeln('Yes') else writeln('No');
end;
end.
最新文章
- 被误解的MVC和被神化的MVVM(转)
- golang 自定义封包协议(转的)
- SpringBoot之springfox(Swagger) (ApiDoc接口文档)
- iOS开发项目之二 [ App appicon与启动图]
- Asp.Net 操作word 第二篇[推荐]
- 将.lib库文件转换成.a库文件的工具
- 比如在vi中按ctrl+z
- android导航设计
- MongoDB【第二篇】集群搭建
- xBIM 插入复制功能
- 【vue】iView-admin2.0动态菜单路由
- IntelliJ IDEA 创建 Maven简单项目
- windows 下面安装make
- jdk安装路径
- sync;sync;sync;reboot
- Linux yum安装MySQL5.7
- 调用百度api输出地址和城市查询出具体坐标系
- thinkphp5动态生成二维码实例总结
- 理解clear:both属性(转)
- [翻译] VBFPopFlatButton
热门文章
- 可扩展的listview--Expandablelistview
- [转]ODBC连接ORACLE数据库的设置
- [引]MSDN Visual Basic 和 C# 中都会用到的编程概念
- RPC之Thrift学习实战
- [记录]java.math.biginteger cannot be cast to java.lang.long
- ASP怎样获得代码中第一张图片地址
- android apk 防止反编译技术第一篇-加壳技术
- WCF编程系列(一)初识WCF
- 再也不要看到Eclipse万恶的arg0,arg1提示
- 暑假集训(2)第八弹 ----- Hero(hdu4310)