哈密尔顿环 dfs

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N = 25;
 6 int n, cnt;
 7 int a[N][N];
 8 int v[N], p[N];
 9 
10 void print(){
11     printf("Route #%d: ", ++cnt);//路径条数 
12     for(int i=1; i<=p[0]; i++) printf("%d - ", p[i]);
13     printf("1\n");
14 }
15 
16 void dfs(int x){
17     v[x] = 1, p[++p[0]] = x;
18     if(p[0] == n)    {
19         if(a[p[0]][1]) print();
20     }
21     else for(int i=1; i<=n; i++)
22     if(a[x][i] && !v[i]) dfs(i);
23     v[x] = 0, p[p[0]] = 0, --p[0];//回溯过程 
24 }
25 
26 int main(){
27     scanf("%d", &n);
28     for(int i=1; i<=n; i++)
29     for(int j=1; j<=n; j++)
30     scanf("%d", &a[i][j]);//输入一个表示i，j之间是否有边的矩阵 
31     dfs(1);
32     return 0;
33 }