POJ - 2438 哈密顿回路遍历

  1 /*
  2 POJ - 2438 哈密顿回路
  3 图的可行遍问题：一般就是哈密顿图和欧拉图
  4 这类问题，代码和算法本身简单，关键就在于建模。
  5 一般判断问题只要判断是否可行遍历！
  6 但是有的时候会有奇葩的要求：
  7 例如：遍历一张欧拉回路图:深度遍历不回溯法，o(n)
  8       遍历哈密顿回路：这道题
  9 言归正传：
 10 1、哈密顿图定义：从一个点出发、经过所有的点必须且只能一次，最终回到起点。图中有边可以不经过，但是不能经过两次。
 11 2、存在的充分条件：图有n个顶点，如果图中任意两个不同的顶点的度数之和大于等于n,则图是哈密顿图。
 12 3、遍历哈密顿图的算法：如下
 13 
 14 解题思路：
 15 1、题目是说，小朋友围一圈坐着，仇恨的不能坐在一起，让你安排座位。
 16 2、建图:可以连着坐的点连一条线，这道题就是求一个哈密顿的可行遍历。
 17 3、判断是否有解：因为每个人最多有n-1个敌人，然而有2*n个小朋友，满足上述充分条件，必然有解。
 18 
 19 */
 20 #include <iostream>
 21 #include <string.h>
 22 #include <stdio.h>
 23 #include <cmath>
 24 #include <vector>
 25 #define LL long long
 26 #define maxn 410
 27 using namespace std;
 28 
 29 bool map[maxn][maxn];
 30 int ans[maxn];
 31 inline void reverse(int s,int t){
 32     while(s<t){
 33         swap(ans[s],ans[t]);
 34         s++;t--;
 35     }
 36 }
 37 void Hamilton(int n){
 38     int s=1,t;
 39     int ansi=2;
 40     int w,i,j;
 41     bool visit[maxn]={false};
 42     for(i=1;i<=n;i++){
 43         if (map[s][i]) break;
 44     }
 45     t=i;
 46     visit[s]=visit[t]=true;
 47     ans[0]=s;
 48     ans[1]=t;
 49     while(1){
 50         while(1){
 51             for(i=1;i<=n;i++){
 52                 if (map[t][i] && !visit[i]){
 53                     ans[ansi++]=i;
 54                     visit[i]=true;
 55                     t=i;
 56                     break;
 57                 }
 58             }
 59             if (i>n) break;
 60         }
 61         w=ansi-1;
 62     i=0;reverse(i,w);
 63     swap(s,t);
 64     while(1){
 65         for(i=1;i<=n;i++){
 66             if (map[t][i] && !visit[i]){
 67                 ans[ansi++]=i;
 68                 visit[i]=true;
 69                 t=i;
 70                 break;
 71             }
 72         }
 73         if (i>n) break;
 74     }
 75     if (!map[s][t]){
 76         for(i=1;i<ansi-2;i++) if (map[ans[i]][t] && map[s][ans[i+1]]) break;
 77         w=ansi-1;
 78         i++;
 79         t=ans[i];
 80         reverse(i,w);
 81     }
 82     if (ansi==n) return ;
 83     for(j=1;j<=n;j++){
 84         if (visit[j]) continue;
 85         for(i=1;i<ansi-2;i++) if (map[ans[i]][j]) break;
 86         if (map[ans[i]][j]) break;
 87     }
 88     s=ans[i-1];
 89     t=j;
 90     reverse(0,i-1);
 91     reverse(i,ansi-1);
 92     ans[ansi++]=j;
 93     visit[j]=true;
 94     }
 95 }
 96 int n,m;
 97 int main(){
 98     while(cin>>n>>m){
 99         if (n==0 && m==0) break;
100         memset(map,0,sizeof(map));
101         for(int i=1;i<=m;i++){
102             int u,v;
103             scanf("%d%d",&u,&v);
104             map[u][v]=map[v][u]=true;
105         }
106         for(int i=1;i<=2*n;i++){
107             for(int j=1;j<=2*n;j++)
108             if (i==j) continue;
109             else map[i][j]=!map[i][j];
110         }
111         Hamilton(2*n);
112         for(int i=0;i<2*n;i++)
113         if (i!=2*n-1) printf("%d ",ans[i]);else printf("%d\n",ans[i]);
114     }
115     return 0;
116 }