波波老师这是我的哈密顿回路c++源程序，你看看对不对？

Question

//旅行商问题之一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
int g[101][101],n,m,length,x,start;
bool v1[101];
int ans[101],num[101];
void print()  //打印结果
{    int i;
     for (i = 1; i <= length; i++)
         cout << ' ' << ans[i];
     cout << endl;   
}
bool allvisited(){  //全部被访问？yes： no
	for(int i=1;i<=n;i++)
		if (v1[i]==0) return false;
	return true;
}
bool dfs(int last,int i)//last是i顶点的父亲结点，从i顶点开始dfs
{
    v1[i] = true;       //访问i顶点
    ans[++length] = i;           //保存i到数组 
    for (int j = 1; j <= num[i]; j++)  { 
    	if (g[i][j]==start&&allvisited())  //**g[i][]数组，表示出i出发的点**
          {
  			ans[++length] = g[i][j];  
        	print();            
  			length--;
  		} 
		if (!v1[g[i][j]]) 
		  	if (dfs(i,g[i][j])) return true;
    }
    length--;
    v1[i] = false; 
    return false;
} 
int main(){

    memset(v1,false,sizeof(v1));
    cin>>n>>m;    //n个结点m条边
	for(int i=1;i<=m;i++){  
		int x,y;
		cin>>x>>y;
		g[x][++num[x]]=y;  //**从x出发的边放进二维数组，共num[x]条**
		g[y][++num[y]]=x;
	}
	start=1;
	dfs(1,start);  //从一号点开始深度优先搜索
    return 0;
}

/*第一个样例
4 5
1 2
1 3
1 4
2 3
2 4
两条哈密尔顿回路
1 3 2 4 1
1 4 2 3 1
哈密尔顿12面体的样例 20个点，30条边
20 30
1 2
1 5
1 14
2 3
2 12
3 10
3 4
4 5
4 8
5 6
6 7
6 15
7 8
7 17
8 9
9 10
9 18
10 11
11 12
11 19
12 13
13 14
13 20
14 15
15 16
16 17
16 20
17 18
18 19
19 20
¹þÃܶû¶Ù»Ø·
1 2 3 10 9 8 4 5 6 7 17 18 19 11 12 13 20 16 15 14 1
1 2 3 10 9 18 17 7 8 4 5 6 15 16 20 19 11 12 13 14 1
1 2 3 10 9 18 17 16 20 19 11 12 13 14 15 6 7 8 4 5 1
1 2 3 10 9 18 19 11 12 13 20 16 17 7 8 4 5 6 15 14 1
1 2 3 10 11 12 13 14 15 6 7 17 16 20 19 18 9 8 4 5 1
1 2 3 10 11 12 13 20 19 18 9 8 4 5 6 7 17 16 15 14 1
1 2 3 4 5 6 7 8 9 10 11 12 13 20 19 18 17 16 15 14 1
1 2 3 4 5 6 15 16 20 19 18 17 7 8 9 10 11 12 13 14 1
1 2 3 4 8 7 17 16 20 19 18 9 10 11 12 13 14 15 6 5 1
1 2 3 4 8 9 10 11 12 13 14 15 16 20 19 18 17 7 6 5 1
1 2 12 11 10 3 4 5 6 15 16 17 7 8 9 18 19 20 13 14 1
1 2 12 11 10 3 4 8 9 18 19 20 13 14 15 16 17 7 6 5 1
1 2 12 11 19 18 9 10 3 4 8 7 17 16 20 13 14 15 6 5 1
1 2 12 11 19 18 17 7 8 9 10 3 4 5 6 15 16 20 13 14 1
1 2 12 11 19 18 17 16 20 13 14 15 6 7 8 9 10 3 4 5 1
1 2 12 11 19 20 13 14 15 16 17 18 9 10 3 4 8 7 6 5 1
1 2 12 13 14 15 6 7 8 9 18 17 16 20 19 11 10 3 4 5 1
1 2 12 13 14 15 16 20 19 11 10 3 4 8 9 18 17 7 6 5 1
1 2 12 13 20 16 17 7 8 9 18 19 11 10 3 4 5 6 15 14 1
1 2 12 13 20 19 11 10 3 4 5 6 7 8 9 18 17 16 15 14 1
1 5 4 3 2 12 11 10 9 8 7 6 15 16 17 18 19 20 13 14 1
1 5 4 3 2 12 13 20 16 17 18 19 11 10 9 8 7 6 15 14 1
1 5 4 3 10 9 8 7 6 15 14 13 20 16 17 18 19 11 12 2 1
1 5 4 3 10 11 19 20 16 17 18 9 8 7 6 15 14 13 12 2 1
1 5 4 8 7 6 15 14 13 12 11 19 20 16 17 18 9 10 3 2 1
1 5 4 8 7 6 15 16 17 18 9 10 3 2 12 11 19 20 13 14 1
1 5 4 8 9 10 3 2 12 11 19 18 17 7 6 15 16 20 13 14 1
1 5 4 8 9 18 17 7 6 15 16 20 19 11 10 3 2 12 13 14 1
1 5 4 8 9 18 19 11 10 3 2 12 13 20 16 17 7 6 15 14 1
1 5 4 8 9 18 19 20 16 17 7 6 15 14 13 12 11 10 3 2 1
1 5 6 7 8 4 3 2 12 13 20 19 11 10 9 18 17 16 15 14 1
1 5 6 7 8 4 3 10 9 18 17 16 15 14 13 20 19 11 12 2 1
1 5 6 7 17 16 15 14 13 20 19 18 9 8 4 3 10 11 12 2 1
1 5 6 7 17 18 9 8 4 3 10 11 19 20 16 15 14 13 12 2 1
1 5 6 7 17 18 19 11 10 9 8 4 3 2 12 13 20 16 15 14 1
1 5 6 7 17 18 19 20 16 15 14 13 12 11 10 9 8 4 3 2 1
1 5 6 15 14 13 12 11 10 9 18 19 20 16 17 7 8 4 3 2 1
1 5 6 15 14 13 20 16 17 7 8 4 3 10 9 18 19 11 12 2 1
1 5 6 15 16 17 7 8 4 3 2 12 11 10 9 18 19 20 13 14 1
1 5 6 15 16 20 19 11 10 9 18 17 7 8 4 3 2 12 13 14 1
1 14 13 12 2 3 10 11 19 20 16 15 6 7 17 18 9 8 4 5 1
1 14 13 12 2 3 4 8 7 17 18 9 10 11 19 20 16 15 6 5 1
1 14 13 12 11 10 9 8 7 17 18 19 20 16 15 6 5 4 3 2 1
1 14 13 12 11 19 20 16 15 6 5 4 8 7 17 18 9 10 3 2 1
1 14 13 20 16 15 6 5 4 3 10 9 8 7 17 18 19 11 12 2 1
1 14 13 20 16 15 6 7 17 18 19 11 12 2 3 10 9 8 4 5 1
1 14 13 20 19 11 12 2 3 10 9 18 17 16 15 6 7 8 4 5 1
1 14 13 20 19 18 9 8 7 17 16 15 6 5 4 3 10 11 12 2 1
1 14 13 20 19 18 9 10 11 12 2 3 4 8 7 17 16 15 6 5 1
1 14 13 20 19 18 17 16 15 6 7 8 9 10 11 12 2 3 4 5 1
1 14 15 6 5 4 3 10 11 19 18 9 8 7 17 16 20 13 12 2 1
1 14 15 6 5 4 8 7 17 16 20 13 12 11 19 18 9 10 3 2 1
1 14 15 6 7 8 9 10 11 19 18 17 16 20 13 12 2 3 4 5 1
1 14 15 6 7 17 16 20 13 12 2 3 10 11 19 18 9 8 4 5 1
1 14 15 16 17 7 6 5 4 8 9 18 19 20 13 12 11 10 3 2 1
1 14 15 16 17 18 9 8 7 6 5 4 3 10 11 19 20 13 12 2 1
1 14 15 16 17 18 9 10 11 19 20 13 12 2 3 4 8 7 6 5 1
1 14 15 16 17 18 19 20 13 12 11 10 9 8 7 6 5 4 3 2 1
1 14 15 16 20 13 12 2 3 4 8 9 10 11 19 18 17 7 6 5 1
1 14 15 16 20 13 12 11 19 18 17 7 6 5 4 8 9 10 3 2 1

*/

1.问题一：这个程序对不对？我检查过是对的，您给看看？
2.为什么你上课只会打印出一条答案？

Answer 1

liuyubobobo 2020-10-28 21:19:25

1

目测没有问题。在 Leetcode 上有哈密顿回路（或者路径）的问题，你可以使用你的逻辑，试一下能否通过这些问题。比如这里：https://leetcode.com/problems/find-the-shortest-superstring/

2

因为在我的代码中，一旦找到一条回路，直接就返回了。

继续加油！：）