dtcms 模板下载 数据库 双重检验锁 dedecms docker容器 swift dataframe tkinter stream Fries vue最新版本 jquery绑定click事件 mysql自连接 不用u盘装双系统 input边框颜色 oracle行转列函数 python逻辑运算符 python写脚本 python中文教程 python环境变量配置 java斐波那契数列 java查看版本 java格式化字符串 黑客攻防实战入门 51脚本 max电池容量 选项卡 英雄联盟体验服转换器 英雄联盟崩溃 ram容量是什么意思 微信临时链接多久失效 polyworks pycharm中文版 html5制作 死从天降成就 苹果手机怎么滚动截屏 pr旋转视频 谷歌浏览器升级 python去重 汪文君
当前位置: 首页 > 学习教程  > 编程语言

18--------------并查集,走亲戚

2021/2/13 20:20:12 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目: http://acm.zzu.edu.cn/problem.php?cid1049&pid4 问题 E: 亲戚 时间限制: 1 Sec 内存限制: 128 MB 提交: 68 解决: 17 [提交] [状态] [讨论版] [命题人:201878030140] 题目描述 或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父…

题目:
http://acm.zzu.edu.cn/problem.php?cid=1049&pid=4

问题 E: 亲戚
时间限制: 1 Sec 内存限制: 128 MB
提交: 68 解决: 17
[提交] [状态] [讨论版] [命题人:201878030140]
题目描述
或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。在这种情况下,最好的帮手是计算机。
为了将问题简化,你将得到一些亲戚关系的信息,如同Xuebin和Grant是亲戚,Grant和Tension是亲戚等,从这些信息中,你可以推出xuebin和Tension是亲戚。请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。

输入
输入由两部分组成:
第一部分以N、M开始。N为问题涉及到的人的个数(1<N<20000)。这些人的编号为1、2、3、…、N。下面有M行(1<M<1000000),每行有两个数ai、bi,表示已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问(1<Q<1000000),每行为ci、di,表示询问ci和di是否为亲戚。

输出
输出有若干行,
对于每个询问ci、di,若ci和di为亲戚,则输出Yes,否则输出No。

样例输入
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

样例输出
Yes
No
Yes

[提交][状态]

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx=2e4+5;
int father[maxx];
int f(int x){
	if(father[x]==x) return x;
	else return father[x]=f(father[x]);//不能写成 f(father[x]),一定要对father[x]进行修改,要不然时间会超限。 
}
void unioni(int a,int b){
	int fa=f(a);
	int fb=f(b);
	if(fa!=fb) father[fa]=fb;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) father[i]=i;
	 for(int i=1;i<=m;i++){
	 	int x,y;
	 	cin>>x>>y;
	 	unioni(x,y);
	 }
	 int q;
	 scanf("%d",&q);
	 for(int i=1;i<=q;i++){
	 	int s,d;
	 	scanf("%d%d",&s,&d);
	 	if(f(s)==f(d)) printf("Yes\n");
	 	else printf("No\n");
	 }
   	
   return 0;
} 

全篇用了scanf和printf,是为了节省时间,否则时间超限。


本文链接: http://www.dtmao.cc/news_show_700444.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?