G - 小希的迷宫

时间:2022-08-29 15:33:24
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房 间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走 了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从 5到达8。
G - 小希的迷宫
 

Input

输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。

整个文件以两个-1结尾。
 

Output

对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。
 

Sample Input

6 8 5 3 5 2 6 4
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

Yes Yes No
 
 
 
数据结构基础题:运用并查集来检查两个点之间是否有两条以上的路,这里特别要注意的是有可能”存在两个集合“,因此我是最后用一个vis[],和ans以及判断是否father[i]==i
来计算集合的个数(ans).
 
 #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 - 小希的迷宫的更多相关文章

  1. G - 小希的迷宫(并查集)

    1今天准备复习三道以前做过的题呢,结果只看了一道,也因为交题的时候没把测试时候为了方便而改的数字改过来而wrong answer,浪费了好长时间,啊啊啊~~ 不过这道题应该是掌握了,嘿嘿…… Desc ...

  2. HDU 1272 小希的迷宫 并查集

    小希的迷宫 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submi ...

  3. hdu 1272 小希的迷宫

    小希的迷宫 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submi ...

  4. 小希的迷宫(MST单棵树判断法则)

    小希的迷宫 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submi ...

  5. hdu 1272 小希的迷宫 解题报告

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1272 第二条并查集,和畅通工程的解法类似.判断小希的迷宫不符合条件,即有回路.我的做法是,在合并两个集 ...

  6. hdu 1257 小希的迷宫 并查集

    小希的迷宫 Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1272 D ...

  7. HDU 1272 小希的迷宫 (并查集)

    小希的迷宫 题目链接: http://acm.hust.edu.cn/vjudge/contest/123393#problem/L Description 我们的小伙伴Bingo身为大二学长,他乐于 ...

  8. 小希的迷宫(HDU 1272 并查集判断生成树)

    小希的迷宫 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submi ...

  9. 小希的迷宫--hdu1272&lpar;并查集&rpar;

    小希的迷宫 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submi ...

随机推荐

  1. odoo注销后在登录时的用户名和密码

    初识odoo时会遇到注销后无法登陆的情况,一般原因是没有留意管理员邮件地址和对应的密码所致.初始情况下默认的邮件地址为admin,密码为数据库创建时提供的密码.

  2. Codevs 1039 &colon;数的划分

    总时间限制: 1000ms 内存限制:  65536kB 描述 将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序). 例如:n=7,k=3,下面三种分法被认为是相同的. 1,1,5: 1 ...

  3. &lpar;转&rpar;嵌入式学习准备---linux c 文件锁

    (1)fcntl函数说明 前面的这5个基本函数实现了文件的打开.读写等基本操作,这一节将讨论的是,在文 件已经共享的情况下如何操作,也就是当多个用户共同使用.操作一个文件的情况,这时,Linux 通常 ...

  4. HTML5面试题-备

    万不可投机取巧.只求当时过关,非长久之计也!(感谢大神分享) 面试有几点需要注意: 面试题目: 根据你的等级和职位变化,入门级到专家级:范围↑.深度↑.方向↑. 题目类型: 技术视野.项目细节.理论知 ...

  5. find、findIndex、indexOf、lastIndex、includes 数组五种查询条件方法介绍

    find() 方法返回数组中满足提供的测试函数的第一个元素的值. 语法: arr.find(callback[, thisArg]) findIndex()方法返回数组中满足提供的测试函数的第一个元素 ...

  6. ap&period;net core 教程(三) - 新建项目

    ASP.NET Core - 新建项目 在这一章,我们将讨论如何在Visual Studio中创建一个新项目. 只要你安装了Visual Studio 2015的.net core工具,您就可以开始构 ...

  7. &lbrack;翻译&rsqb;现代java开发指南 第三部分

    现代java开发指南 第三部分 第三部分:Web开发 第一部分,第二部分,第三部分 =========================== 欢迎来到现代 Java 开发指南第三部分.在第一部分中,我们 ...

  8. Java不走弯路教程(1&period;环境搭建)

    1.环境搭建在开始写第一个Java程序之前,我们需要做一些简单的准备工作. 1.1 还记得DOS吗 我们可以通过图形界面来操作我们的电脑.但作为程序员,你首先需要学会用命令行的方式来操作电脑,因为不是 ...

  9. python函数用法

    一.定义函数 形参:函数完成一项工作所需要的信息,在函数定义时完成 实参:调用函数时传递给函数的信息 二.传递实参 1.位置实参:每个实参都关联到函数定义中的一个形参 示例: def describe ...

  10. MDP安装之数据库

    /usr/bin/mysqladmin -u root password 'Bic2017' mysql-community-client-5.6.28-2.el6.x86_64 mysql-comm ...