http://acm.hdu.edu.cn/showproblem.php?pid=5424
哈密顿通路：联通的图，访问每个顶点的路径且只访问一次
n个点n条边
n个顶点有n - 1条边，最后一条边的连接情况：
(1)自环（这里不需要考虑)；
(2)最后一条边将首和尾连接，这样每个点的度都为2；
(3)最后一条边将首和除尾之外的点连接或将尾和出尾之外的点连接，这样相应的首或尾的度最小，度为1；
(4)最后一条边将首和尾除外的两个点连接，这样就有两个点的度最小，度都为1
如果所给的图是联通的话，那么其度为1的点最多有2个，否则该图不连通
以度最小的点为起点进行DFS判断是否为哈密顿通路
哈密顿通路介绍：
https://en.wikipedia.org/wiki/Hamiltonian_path
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define N 1010
#define INF 0x3f3f3f3f using namespace std; int n, G[N][N], du[N], f;
bool vis[N]; void Init()
{
memset(G, , sizeof(G));
memset(du, , sizeof(du));//du[i]记录点i的入度
memset(vis, false, sizeof(vis));
} void DFS(int u, int cnt)
{
int i;
vis[u] = true;
if(cnt == n)//访问次数与点的个数相等，则每个点都访问到了，且每个点只访问了一次
{
f = ;
return ;
}
for(i = ; i <= n && !f ; i++)
{
if(!vis[i] && G[u][i])
{
DFS(i, cnt + );
vis[i] = false;
}
}
} int main()
{
int u, v, i;
while(~scanf("%d", &n))
{
Init();
for(i = ; i <= n ; i++)
{
scanf("%d%d", &u, &v);
if(u != v && !G[u][v])//去除自环和重边的情况
{
G[u][v] = G[v][u] = ;
++du[u];
++du[v];
}
}
int s = , num = ;//s记录度最小的点
for(i = ; i <= n ; i++)
{
if(du[i] == )
{
num++;//统计度为1的点的个数
s = i;
}
}
if(num > )
{
printf("NO\n");//判断其不连通，则不是哈密顿通路
continue;
}
f = ;
DFS(s, );//从度最小的开始搜
if(f == )
printf("YES\n");
else
printf("NO\n");
}
return ;
}