题意:给n个点n条边,判断图是否为哈密顿通路。

直接暴力搜

//author: CHC
//First Edit Time: 2015-08-30 16:12
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1010;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN*2];
int head[MAXN],tot;
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
}
int vis[MAXN],n;
void dfs1(int u){
vis[u]=1;
for(int i=head[u];~i;i=e[i].next){
if(!vis[e[i].to])dfs1(e[i].to);
}
}
bool dfs2(int u,int d){
if(d==n) return true;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(dfs2(v,d+1))return true;
vis[v]=0;
}
}
return false;
}
int mapp[MAXN][MAXN],du[MAXN];
int main()
{
while(~scanf("%d",&n)){
memset(mapp,0,sizeof(mapp));
for(int i=1;i<=n;i++) mapp[i][i]=1;
memset(du,0,sizeof(du));
init();
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(!mapp[x][y]){
mapp[x][y]=mapp[y][x]=1;
AddEdge(x,y);
++du[x];++du[y];
}
}
memset(vis,0,sizeof(vis));
dfs1(1);
int s=1,flag=0,cnt1=0,cnt3=0;
for(int i=1;i<=n;i++){
if(!vis[i])flag=1;
if(du[s]>du[i])s=i;
if(du[i]==1)++cnt1;
else if(du[i]==3)++cnt3;
else if(du[i]==0&&n!=1)flag=1;
if(cnt1>2)flag=1;
if(cnt3>2)flag=1;
}
//printf("s:%d\n",s);
memset(vis,0,sizeof(vis));
vis[s]=1;
if(flag)puts("NO");
else if(dfs2(s,1))puts("YES");
else puts("NO");
}
return 0;
}