哈密尔顿环
欧拉回路是指不重复地走过所有路径的回路,而哈密尔顿环是指不重复地走过所有的点,并且最后还能回到起点的回路。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int num[10001];//求一个点能过到达的边的数量
5 int map[1001][1001];
6 int jztx[1001];
7 int vis[1001];
8 int now=1;
9 int ans[1001];
10 int x;
11 void print()
12 {
13 for(int i=1;i<=now-1;i++)
14 cout<<ans[i]<<" ";
15 cout<<endl;
16 }
17 void dfs(int last,int i)// last为上一次访问的节点,避免出现圆环首尾相连的情况,,i是当前访问的点
18 {
19 jztx[i]=1;
20 vis[i]=1;
21 ans[now]=i;
22 now++;
23 for(int j=1;j<=num[i];j++)
24 {
25 if(map[i][j]==x&&map[i][j]!=last)
26 {
27 ans[now]=map[i][j];
28 now++;
29 print();
30 now--;
31 break;
32 }
33 if(vis[map[i][j]]==0)
34 {
35 dfs(i,map[i][j]);
36 }
37 }
38 now--;
39 vis[i]=0;
40 }
41 int main()
42 {
43 int n,m;
44 scanf("%d%d",&n,&m);
45 for(int i=1;i<=m;i++)
46 {
47 int x,y;
48 scanf("%d%d",&x,&y);
49 map[x][++num[x]]=y;
50 map[y][++num[y]]=x;
51 }
52 for(x=1;x<=n;x++)
53 if(jztx[x]==0)
54 {
55 now=1;
56 dfs(0,x);
57 }
58 return 0;
59 }