判断是否存在哈密顿路--HDU 5424

题意：给一张无向图，判断是否是哈密顿图。

哈密顿路：经过每个点有且仅有一次的一条通路。

方法：每次找度数最小的点作为起点，然后dfs整个图，看能遍历到的点的数目能否达到n。

 #include<iostream>

 #include<cstdio>

 #include<ctime>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<climits>

 #include<set>

 using namespace std;

 const int maxn=,inf=1E9;

 vector<int>g[maxn];

 int n,vis[maxn],dep,cnt;

 bool dfs(int u)

 {

     if(dep == n)

         return true;

     for(int i=; i<g[u].size(); i++)

     {

         int v = g[u][i];

         if(vis[v])

             continue;

         vis[v] = true;

         dep++;

         if(dfs(v))

             return true;

         dep -- ;

         vis[v] = ;

     }

     return false;

 }

 int main()

 {

     int u,v;

     while(scanf("%d",&n) != -)

     {

         for(int i=; i<=n; i++)

             g[i].clear();

         for(int i=; i<=n; i++)

         {

             scanf("%d%d",&u,&v);

             g[u].push_back(v);

             g[v].push_back(u);

         }

         int head=,cnt=;

         for(int i=; i<=n; i++)

             if(g[i].size() == )

             {

                 head=i;///找起点

                 cnt++;

             }

         if(cnt>)///如果度数为1的点超过两个

         {

             puts("NO");

             continue;

         }

         memset(vis,,sizeof(vis));

         if(head == )

             head=;///没有度数为1，即是个环

         dep=;

         if(dfs(head))

             puts("YES");

         else puts("NO");

     }

 }