哈密顿图 BestCoder Round #53 (div.2) 1003 Rikka with Graph II

 

题目传送门

题意：判断是否为哈密顿图

分析：首先一种情况是不合法的：也就是度数为1的点超过2个；合法的有：，那么从度数为1的点开始深搜，如果存在一种走法能够走完n个点那么存在哈密顿路

收获：学习资料

 

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015-8-29 20:37:34
* File Name     :C.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
vector<int> G[N];
bool vis[N];
int n;

bool DFS(int u, int dep)  {
    if (dep == n)   return true;
    for (int i=0; i<G[u].size (); ++i)    {
        int v = G[u][i];
        if (vis[v]) continue;
        vis[v] = true;
        if (DFS (v, dep + 1))   return true;
        vis[v] = false;
    }
    return false;
}

int main(void)    {
    while (scanf ("%d", &n) == 1)   {
        for (int i=1; i<=n; ++i)    G[i].clear ();
        for (int u, v, i=1; i<=n; ++i)  {
            scanf ("%d%d", &u, &v);
            G[u].push_back (v);
            G[v].push_back (u);
        }
        bool flag = true;
        int s = 0, cnt = 0;
        for (int i=1; i<=n; ++i)    {
            if (G[i].size () == 1)  {
                s = i;  cnt++;
            }
        }
        if (cnt > 2)    {
            puts ("NO");    continue;
        }
        if (cnt == 0) s = 1;
        memset (vis, false, sizeof (vis));  vis[s] = true;
        if (!DFS (s, 1))   flag = false;
        puts (flag ? "YES" : "NO");
    }

    return 0;
}