hdu 5424 Rikka with Graph II(dfs+哈密顿路径)

时间:2022-08-28 10:46:05
Problem Description
 
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path.
It is too difficult for Rikka. Can you help her?
Input
There are no more than  testcases.
For each testcase, the first line contains a number n(≤n≤).
Then n lines follow. Each line contains two numbers u,v(≤u,v≤n) , which means there is an edge between u and v.
Output
For each testcase, if there exist a Hamiltonian path print "YES" , otherwise print "NO".
 
Sample Input

 
Sample Output
NO 
YES
Hint For the second testcase, One of the path is 1->2->3 If you doesn't know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path).
 
Source
 
 

给一个n条边,n个顶点的图,判定是否存在哈密顿路。

 

如果存在哈密顿路,此时路径中含有n-1条边,剩下的那一条要么是自环(这里不予考虑,因为哈密顿路必然不经过),要么连接任意两个点。不考虑自环,此时图中的点度数为1的个数必然不超过2个,有如下三种情况:

1、剩下的那条边连接起点和终点,此时所有点度数都是2,可以从任意一个顶点开始进行DFS,看能否找到哈密顿路

2、剩下的那条边连接除起点和终点外的任意两个点,此时起点和终点度数为1,任选1个开始进行DFS。

3、剩下的那条边连接起点和除终点的任意一个点,或者连接终点与除起点外的任意一个点,此时图中仅有1个点度数为1,从该点开始进行DFS即可。

 
 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[][];
int dgree[];
int vis[];
int n;
int f;
void dfs(int x)
{
vis[x]=;
for(int i=;i<=n;i++)
{
if(!vis[i] && map[x][i])
{
dfs(i);
vis[i]=;
}
}
}
void dfs1(int u,int num){
if(num==n){
f=;
return;
}
for(int i=;i<=n;i++){
if(!vis[i] && map[u][i]){
vis[i]=;
dfs1(i,num+);
if(f)
return;
vis[i]=;
}
}
}
int main()
{
int t; int x,y;
while(scanf("%d",&n)==)
{
memset(vis,,sizeof(vis));
memset(map,,sizeof(map));
memset(dgree,,sizeof(dgree));
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=;
++dgree[x];
++dgree[y];
}
dfs();
int flag=;
int count=;
for(int i=;i<=n;i++)
{
if(!vis[i])
{
flag=;
break;
}
if(dgree[i]==)
{
count++;
}
}
if(flag== || count>)
{
printf("NO\n");
continue;
}
if(count==)
{
printf("YES\n");
}
else {
f=;
for(int i=;i<=n;i++){
if(dgree[i]==){
memset(vis,,sizeof(vis));
vis[i]=;
dfs1(i,);
if(f)
break;
}
}
if(f) puts("YES");
else puts("NO");
} }
return ;
}
 

hdu 5424 Rikka with Graph II(dfs+哈密顿路径)的更多相关文章

  1. HDU 5424——Rikka with Graph II——————【哈密顿路径】

    Rikka with Graph II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe ...

  2. hdu 5424 Rikka with Graph II &lpar;BestCoder Round &num;53 &lpar;div&period;2&rpar;&rpar;&lpar;哈密顿通路判断)

    http://acm.hdu.edu.cn/showproblem.php?pid=5424 哈密顿通路:联通的图,访问每个顶点的路径且只访问一次 n个点n条边 n个顶点有n - 1条边,最后一条边的 ...

  3. HDU 5424 Rikka with Graph II

    题目大意: 在 N 个点 N 条边组成的图中判断是否存在汉密尔顿路径. 思路:忽略重边与自回路,先判断是否连通,否则输出"NO",DFS搜索是否存在汉密尔顿路径. #include ...

  4. HDU 5831 Rikka with Parenthesis II(六花与括号II)

    31 Rikka with Parenthesis II (六花与括号II) Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536 ...

  5. HDU 5831 Rikka with Parenthesis II (栈&plus;模拟)

    Rikka with Parenthesis II 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5831 Description As we kno ...

  6. hdu 5831 Rikka with Parenthesis II 线段树

    Rikka with Parenthesis II 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5831 Description As we kno ...

  7. HDU 5631 Rikka with Graph 暴力 并查集

    Rikka with Graph 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5631 Description As we know, Rikka ...

  8. HDU 5422 Rikka with Graph

    Rikka with Graph Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) ...

  9. HDU 6090 Rikka with Graph

    Rikka with Graph 思路: 官方题解: 代码: #include<bits/stdc++.h> using namespace std; #define ll long lo ...

随机推荐

  1. JAVA软件开发职责

    1.了解OO,AOP,SOA设计模式.J2EE的核心设计模式.应用架构模式和应用集成模式:2.熟练使用Spring.Hibernate/ibatis.Struts等通用性开源框架,并对其原理有深刻的理 ...

  2. 海量Web日志分析 用Hadoop提取KPI统计指标

    http://blog.fens.me/hadoop-mapreduce-log-kpi/ http://dongxicheng.org/search-engine/scribe-installati ...

  3. SQLServer 使用 &commat;&commat;ERROR

    原文:SQLServer 使用 @@ERROR 使用 @@ERROR 如果最后的 Transact-SQL 语句执行成功,则 @@ERROR 系统函数返回 0:如果此语句产生错误,则 @@ERROR ...

  4. &lbrack;extjs5学习笔记&rsqb;第三十七节 Extjs6预览版都有神马新东西

    本文在微信公众号文章地址:微信公众号文章地址 本文地址:http://blog.csdn.net/sushengmiyan/article/details/45190485 [TOC] 在Ext JS ...

  5. C&num; 使用NPOI 处理Excel(Datable与Excel相互转换)

    VS上有自带的程序集可以读取,但是总是会出现这样或那样的问题,让人恨得牙疼!而且效率太慢了.用NPOI就好多了,比较快,而且稳定,还简单,引用相应的程序集就好了. Excel转换成Datable pr ...

  6. MFC中运行出现问题&OpenCurlyDoubleQuote;不支持尝试执行的操作”

    http://blog.csdn.net/maturn/article/details/8051987 问题描述: 基于CDialogEx的对话框工程.VS2010开发环境. 调试运行到OnInitD ...

  7. string替换字符串,路径的斜杠替换为下划线

    场景 替换某个路径的所有"\"为"_". 很多时候取证需要把恶意代码文件取回来,然后清除. 如果在D:\WEB\模板制作插件\需要覆盖\CodeColoring ...

  8. 写一个简单的shellcode

    0x00 前言 漏洞利用中必不可缺的部分就是shellcode,不会编写shellcode和咸鱼有什么区别,跳出咸鱼第一步. 0x01 系统调用 通过系统调用execve函数返回shell C语言实现 ...

  9. iOS10开发需要注意的一些问题&lpar;转&rpar;

    兼容iOS 10 资料整理笔记 2016-09-17 判若两人丶 CocoaChina ▲点击上方“CocoaChina”关注即可免费学习iOS开发 原文链接:http://www.jianshu.c ...

  10. 【转】虚拟化(二):虚拟化及vmware workstation产品使用

    vmware workstation的最新版本是10.0.2.相信大家也都使用过,其中的简单的虚拟机的创建,删除等,都很简单,这里就不再详细说明了,下面我将简单介绍下vmware workstatio ...