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 ;
}