哈密尔顿环

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int num[1001];
 5 bool vis[1001],v1[1001];
 6 int maps[1001][1001],ans[1001];
 7 int start,length=0,saber,x,n;
 8 void print()
 9 {
10     for(int i=1;i<=length;i++)
11     cout<<" "<<ans[i];
12     cout<<endl;
13 }
14 void dfs(int bef,int now)//bef上一个数 
15 {
16     vis[now]=true;
17     v1[now]=true;//biao ji x环以经来过；
18     ans[++length]=now;
19     for(int i=1;i<=num[now];i++)
20     {
21         if(maps[now][i]==x&&maps[now][i]!=bef)//判断构成回路；
22         {
23             ans[++length]=maps[now][i];
24             print();
25             length--;
26             break;
27         }
28         if(!vis[maps[now][i]])
29         dfs(now,maps[now][i]);//遍历与i相关联de点
30     }
31     length--;
32     vis[now]=false;//回溯 
33 }
34 int main()
35 {
36     int m;int z,y;
37     cin>>n>>m;
38     for(int i=1; i<=m; i++) 
39     {
40         cin>>z>>y;
41         maps[z][++num[z]]=y;
42         maps[y][++num[y]]=z;
43     }
44     for(x=1;x<=n;x++)
45         if(!v1[x])//以x为头头的环； 
46         {
47             length=0;
48             dfs(0,x);
49         }
50     return 0; 
51 }