题目基于一个定理：当所有点相连的点的个数大于N/2时，一定可以构造出一条哈密顿回路，构造的复杂度是N^2。
这题的正解是构造，但很多人都是搜索过的，只能说明这题的数据比较水。sgu上有一道基本一样的题目(sgu122)，这一题不用构造是过不了的。
至于构造方法，也就是3步。
STEP1:先找两个相邻点s-t，扩充出一条链直到到不能扩充为止。
STEP2:这时如果s-t不相邻，在链上找一点vi满足s与next[vi]相邻并且vi与t相邻，链转化为s-vi-t-next[vi]-s，根据鸽巢原理这个点必然存在。
STEP3:如果链中的点不足N个，就在环上开一个新口继续加点，重复STEP1~3即可。
1 #include <string.h> 2 #include <stdio.h> 3 #define MAXN 155 4 struct edge{ 5 int v,n; 6 }e[MAXN*MAXN]; 7 int first[MAXN],es; 8 int map[MAXN][MAXN]; 9 int next[MAXN],n_next[MAXN],vis[MAXN]; 10 int n,m,tu,tv; 11 void addedge(int u,int v){ 12 e[es].v=v,e[es].n=first[u],first[u]=es++; 13 } 14 int findadj(int s){ 15 for(int i=first[s];i!=-1;i=e[i].n) 16 if(!vis[e[i].v])return e[i].v; 17 return 0; 18 } 19 int main(){ 20 //freopen("test.in","r",stdin); 21 while(scanf("%d%d",&n,&m)!=EOF){ 22 memset(first,-1,sizeof first);es=0; 23 memset(map,0,sizeof map); 24 for(int i=0;i<m;i++){ 25 scanf("%d%d",&tu,&tv); 26 addedge(tu,tv); 27 addedge(tv,tu); 28 map[tu][tv]=map[tv][tu]=1; 29 } 30 memset(next,0,sizeof next); 31 memset(vis,0,sizeof vis); 32 int s=1,t=e[first[1]].v,x,nodes=2; 33 next[s]=t,vis[s]=vis[t]=1; 34 while(nodes<n){ 35 //扩展s-t链 36 while(x=findadj(s))next[x]=s,s=x,vis[s]=1,nodes++; 37 while(x=findadj(t))next[t]=x,t=x,vis[t]=1,nodes++; 38 //若s-t不相连,在链上找一点v有s-next[v]-t-v-S 39 if(map[s][t]==0){ 40 for(int i=next[s];next[i]!=t;i=next[i]){ 41 if(map[s][next[i]]&&map[i][t]){ 42 for(int j=next[i];j!=t;j=next[j])n_next[next[j]]=j; 43 for(int j=t;j!=next[i];j=n_next[j])next[j]=n_next[j]; 44 x=next[i],next[i]=t,t=x; 45 break; 46 } 47 } 48 } 49 next[t]=s; 50 //若点数小于N,开一个口子继续加点 51 for(int i=s;i!=t;i=next[i]){ 52 if(x=findadj(i)){ 53 s=next[i],t=i; 54 break; 55 } 56 } 57 } 58 for(int i=s;i!=t;i=next[i])printf("%d ",i); 59 printf("%d\n",t); 60 } 61 return 0; 62 }