Description
Input
整个文件以两个-1结尾。
Output
Sample Input
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
Sample Output
#include<cstdio>
#include<string.h>
using namespace std;
//int rank[100010];
int father[];
int max1=;
int vis[];
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
bool Union(int x,int y)
{
int x1=find(x),y1=find(y);
if(x1!=y1)
{
father[y1]=x1;
return true;
//rank[x]+=rank[y];
//if(max1<rank[x]) max1=rank[x];
//return;
}
return false;
}
int main()
{
int a,b;
while(scanf("%d %d",&a,&b)!=EOF&&a!=-&&b!=-)
{
for(int i=;i<=;i++)
father[i]=i;
if(a==&&b==){printf("Yes\n");continue;} //注意continue!!!
int min=;
int max=;
int flag=;
memset(vis,,sizeof(vis));
while(a||b)
{
if(a>max) max=a;
if(b>max) max=b;
if(a<min) min=a;
if(b<min) min=b;
vis[a]=;
vis[b]=;
if(!Union(a,b)) flag=;
scanf("%d %d",&a,&b);
}
if(flag==) printf("No\n");
else{
int ans=;
for(int i=min;i<=max;i++)
if(vis[i]&&father[i]==i)
ans++;
if(ans==) printf("Yes\n");
else printf("No\n");
} }
return ;
}
换了一个小思路
#include<cstdio>
#include<string.h>
using namespace std;
//int rank[100010];
int father[];
int rank[];
int max1=;
//int vis[100010];
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
bool Union(int x,int y)
{
int x1=find(x),y1=find(y);
if(x1!=y1)
{
father[y1]=x1; rank[x1]+=rank[y1];//记录深度
if(max1<rank[x1]) max1=rank[x1];
return true;
//rank[x]+=rank[y];
//if(max1<rank[x]) max1=rank[x];
//return;
}
return false;
}
int main()
{
int a,b;
while(scanf("%d %d",&a,&b)!=EOF&&a!=-&&b!=-)
{
for(int i=;i<=;i++)
{
father[i]=i;rank[i]=;
} if(a==&&b==){printf("Yes\n");continue;}
int flag=;
//memset(vis,0,sizeof(vis));
int ans=;
while(a||b)
{
ans=ans+;//这是记录输入的边的条数
if(!Union(a,b)) flag=;
scanf("%d %d",&a,&b);
}
// printf("%d %d\n",ans,max1);
if(flag==) printf("No\n");
else if(max1-==ans) printf("Yes\n");
else printf("No\n");
}
return ;
}
G - 小希的迷宫的更多相关文章
-
G - 小希的迷宫(并查集)
1今天准备复习三道以前做过的题呢,结果只看了一道,也因为交题的时候没把测试时候为了方便而改的数字改过来而wrong answer,浪费了好长时间,啊啊啊~~ 不过这道题应该是掌握了,嘿嘿…… Desc ...
-
HDU 1272 小希的迷宫 并查集
小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi ...
-
hdu 1272 小希的迷宫
小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi ...
-
小希的迷宫(MST单棵树判断法则)
小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi ...
-
hdu 1272 小希的迷宫 解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1272 第二条并查集,和畅通工程的解法类似.判断小希的迷宫不符合条件,即有回路.我的做法是,在合并两个集 ...
-
hdu 1257 小希的迷宫 并查集
小希的迷宫 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1272 D ...
-
HDU 1272 小希的迷宫 (并查集)
小希的迷宫 题目链接: http://acm.hust.edu.cn/vjudge/contest/123393#problem/L Description 我们的小伙伴Bingo身为大二学长,他乐于 ...
-
小希的迷宫(HDU 1272 并查集判断生成树)
小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi ...
-
小希的迷宫--hdu1272(并查集)
小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi ...
随机推荐
-
odoo注销后在登录时的用户名和密码
初识odoo时会遇到注销后无法登陆的情况,一般原因是没有留意管理员邮件地址和对应的密码所致.初始情况下默认的邮件地址为admin,密码为数据库创建时提供的密码.
-
Codevs 1039 :数的划分
总时间限制: 1000ms 内存限制: 65536kB 描述 将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序). 例如:n=7,k=3,下面三种分法被认为是相同的. 1,1,5: 1 ...
-
(转)嵌入式学习准备---linux c 文件锁
(1)fcntl函数说明 前面的这5个基本函数实现了文件的打开.读写等基本操作,这一节将讨论的是,在文 件已经共享的情况下如何操作,也就是当多个用户共同使用.操作一个文件的情况,这时,Linux 通常 ...
-
HTML5面试题-备
万不可投机取巧.只求当时过关,非长久之计也!(感谢大神分享) 面试有几点需要注意: 面试题目: 根据你的等级和职位变化,入门级到专家级:范围↑.深度↑.方向↑. 题目类型: 技术视野.项目细节.理论知 ...
-
find、findIndex、indexOf、lastIndex、includes 数组五种查询条件方法介绍
find() 方法返回数组中满足提供的测试函数的第一个元素的值. 语法: arr.find(callback[, thisArg]) findIndex()方法返回数组中满足提供的测试函数的第一个元素 ...
-
ap.net core 教程(三) - 新建项目
ASP.NET Core - 新建项目 在这一章,我们将讨论如何在Visual Studio中创建一个新项目. 只要你安装了Visual Studio 2015的.net core工具,您就可以开始构 ...
-
[翻译]现代java开发指南 第三部分
现代java开发指南 第三部分 第三部分:Web开发 第一部分,第二部分,第三部分 =========================== 欢迎来到现代 Java 开发指南第三部分.在第一部分中,我们 ...
-
Java不走弯路教程(1.环境搭建)
1.环境搭建在开始写第一个Java程序之前,我们需要做一些简单的准备工作. 1.1 还记得DOS吗 我们可以通过图形界面来操作我们的电脑.但作为程序员,你首先需要学会用命令行的方式来操作电脑,因为不是 ...
-
python函数用法
一.定义函数 形参:函数完成一项工作所需要的信息,在函数定义时完成 实参:调用函数时传递给函数的信息 二.传递实参 1.位置实参:每个实参都关联到函数定义中的一个形参 示例: def describe ...
-
MDP安装之数据库
/usr/bin/mysqladmin -u root password 'Bic2017' mysql-community-client-5.6.28-2.el6.x86_64 mysql-comm ...