HDUOJ ---1269迷宫城堡
2024-08-25 07:55:52
http://acm.hdu.edu.cn/showproblem.php?pid=1269
迷宫城堡
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5596 Accepted Submission(s): 2482
Problem Description
为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的,即:对于任意的i和j,至少存在一条路径可以从房间i到房间j,也存在一条路径可以从房间j到房间i。
Input
输入包含多组数据,输入的第一行有两个数:N和M,接下来的M行每行有两个数a和b,表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
Output
对于输入的每组数据,如果任意两个房间都是相互连接的,输出"Yes",否则输出"No"。
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
Sample Output
Yes
No
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 10000
int shun[maxn+],fan[maxn+];
void inti(int n)
{
for(int i=;i<=n;i++)
{
shun[i]=i;
fan[i]=i;
}
}
int setfind(int x,int *father)
{
if(x!=father[x]&&father[x]!=) /*以1为root*/
{
father[x]=setfind(father[x],father);
}
return father[x];
}
void colect(int x,int y)
{
/*等于1不处理,是因为以1为root,设1的祖先为自己*/
/*顺反寻找节点*/
if(x>)shun[x]=setfind(y,shun); //去寻找父节点
if(y>)fan[y]=setfind(x,fan); //去寻找父节点
} int main()
{
int m,n,i,a,b;
freopen("test.in","r",stdin);
while(~scanf("%d%d",&n,&m)/*,m+n*/)
{
inti(n);
for(i=;i<m;i++)
{
scanf("%d%d",&a,&b);
colect(a,b);
}
for(i=;i<=n;i++)
{
if(setfind(i,shun)!=||setfind(i,fan)!=)
{
printf("No\n");
break;
} }
if(i>n)
printf("Yes\n");
}
return ;
}
双向查询,看能否回到原点.....
最新文章
- 在Nodejs中如何调用C#的代码
- iOS--- UITableView + UISearchDisplayController - - - - -实现搜索功能
- java Resource
- SQL 报错信息整理及解决方案(持续更新)
- BFS POJ 3278 Catch That Cow
- SQL server 表之间的关系生成图
- Think Python - Chapter 17 - Classes and methods
- 使用Markdown编辑器写博客
- AIR 移动设备上的存储控制
- QL查询案例:取得分组 TOP-N
- Spark(Hive) SQL中UDF的使用(Python)
- asp.net微信开发第四篇----已关注用户管理
- 同台交换机同样VLAN能够通信,不同VLAN不可通信
- JS实现排序
- Python第一行代码
- 201521123090《Java程序设计》第10周学习总结
- JAVA继承:编译与运行的关系(编译看左边,运行看右边)
- Collections.unmodifiableMap(Map map)
- MyBatis笔记----@Intercepts({@Signature(type = StatementHandler.class, method = ";prepare";, args = {Connection.class
- jenkins持续集成:构建多个job同时执行
热门文章
- [Linux] Linux 守护进程的启动方法
- Informatica 常用组件Lookup之三 关系和平面文件查找
- python中 对文件的读写操作 以及如何边写入 边保存flush()
- Ubuntu14.04下Neo4j图数据库官网安装部署步骤(图文详解)(博主推荐)
- 关于json与protobuf的材料
- 关于COM组件log的位置
- 设置网站expires和max-age属性
- idea 设置代码的颜色
- [Node.js]32. Level 7: Working with Lists -- Redis
- Singular value encountered in calculation for ROI