hdoj 1272 小希的迷宫
整个文件以两个-1结尾。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 100010
using namespace std;
int per[N], h[N];//数组per用来记录父节点,h数组用来记录出现的点
void init()//对所有点的父节点进行初始化
{
for(int i = 1; i <= N; i++)
per[i] = i;
}
int find(int x)//利用递归寻找某个点的根节点
{
return x==per[x] ? x : find(per[x]);
}
int join(int x, int y)//判断是否成环
{
int fx = find(x);
int fy = find(y);
if(fx == fy)//因为给的两个点本来就是连通的,如果根节点一样,就成环了
return 0;
else
{
per[fx] = fy;
return 1;
}
}
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m), n!=-1 && m!=-1)
{
memset(h, 0, sizeof(h)); //将数组初始化为0,出现的点就标记为1
if(n == 0 && m == 0)
{
printf("Yes\n");
continue;
}
int flag = 1;
h[n] = 1;
h[m] = 1;
init();
join(n, m);
while(~scanf("%d%d", &n, &m), n&&m)
{
int t = join(n, m);//用t记录是否成环
if(!h[n])
h[n] = 1;
if(!h[m])
h[m] = 1;
if(t == 0)如果成环,就令flag = 0
flag = 0;
}
int root = 0;
for(int i = 1; i <= N; i++)//判断根节点的个数
{
if(h[i] && per[i] == i)
root++;
}
if(flag == 0 || root > 1)//根节点的个数大于1或者成环时输出No
printf("No\n");
else
printf("Yes\n");
}
return 0;
最新文章
- 探究javascript对象和数组的异同,及函数变量缓存技巧
- [WinForm] DataGridView 绑定 DT &;&; ComboBox 列绑定 Dict
- Javascript中JSON对象的操作以及遍历key/value
- 嵌入式linux下如何尽快播放开机音乐
- Python黑帽编程 3.1 ARP欺骗
- RESTful API URI 设计: 查询(Query)和标识(Identify)
- and or bool and a or b 原理解释
- OC ---- 字符串 数组 iOS学习-----细碎知识点总结
- CLR via C#(12)-委托Delegate
- eclipse插件在线发布发布和版本更新(web site) 转
- android 64 sd卡读写的操作
- 写个脚本列出neutron的ovs的topology。
- SVN模型仓库中的资源从一个地方移动到另一个地方的办法(很久才解决)
- Math.round(),Math.ceil(),Math.floor()的区别
- es6 Generator生成器函数
- Binary Tree Xorder Traversal
- JAVA-类方法与实例方法
- Linux命令:typeset
- 查看Sql Server 数据库的内存使用情况
- java内部类及四种内部类的实现方式
热门文章
- 一种table超出高度自动出滚动条的解决方案
- eclipse debug maven项目时出现缺少库的问题
- add number
- ETL利器Kettle
- WCF在tcp通道下启用httpget
- Tcc学习笔记(二) 安装和配置
- iOS的架构
- @RequestMapping(value = ";{adminPath}";)
- less预处理的好处,补充关于之前发表的rem单位的运用于计算
- 转:fatal error: SDL/SDL.h: No such file or directory