Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1051 Accepted Submission(s): 266
#include<bits/stdc++.h>
using namespace std;
const int maxn=2100;
const int INF=0x3f3f3f3f;
int degree[maxn];
int vis[maxn],gra[maxn][maxn];
vector<int>G[maxn];
int n;
bool dfs(int u,int fa,int cn){
if(cn==n){
return true;
}
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vis[v]||v==fa){
continue;
}
vis[v]=1;
if(dfs(v,u,cn+1))
return true;
vis[v]=0; //如果没有这句,会过不了这个样例。5 2 3 2 4 4 1 1 2 5 4
}
return false;
}
void init(){//以后尽量放在前面情况,不装B
for(int i=0;i<=n+2;i++)
G[i].clear();
memset(degree,0,sizeof(degree));
memset(vis,0,sizeof(vis));
memset(gra,0,sizeof(gra));
}
int main(){
int a,b;
while(scanf("%d",&n)!=EOF){
init();
for(int i=0;i<n;i++){
scanf("%d%d",&a,&b);
if(gra[a][b]==1||a==b)
continue;
gra[a][b]=gra[b][a]=1;
G[a].push_back(b);
G[b].push_back(a);
degree[a]++,degree[b]++;
}
int deg1=0,idx=1;
for(int i=1;i<=n;i++){
if(degree[i]==1){
deg1++;
idx=i;
}
}
if(deg1>2){ //度为1的大于2个,必然不行
puts("NO");
continue;
}
vis[idx]=1;
if(dfs(idx,0,1))
puts("YES");
else puts("NO");
}
return 0;
}
HDU 5424——Rikka with Graph II——————【哈密顿路径】
原文:http://www.cnblogs.com/chengsheng/p/4778960.html