1364: 所有可能的路径

http://tjuacm.chaosheng.top/problem.php?id=1364

DFS

能过样例，但WA

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 15;

int n, m;
int vis[N];
int path[N];
int map[N][N];

void dfs(int k){ //从第一个点开始找周围最短的边 
    if(path[k-1] == m && k < m){
        for(int i = 0; i < k-1; i++){
            printf("%d ", path[i]);
        }
        printf("%d\n", path[k-1]);
    }

    if(k == m) return; 

    for(int i = 2; i <= m; i++){
        if(!vis[i] && map[path[k-1]][i] == 1){
            path[k] = i;
            vis[i] = 1;
            dfs(k + 1);
            vis[i] = 0;
        }
    }
}

int main(){
    while(cin >> m >> n){
        int a, b;
        memset(map, 0, sizeof(map));

        for(int i = 1; i <= m; i++){
            cin >> a >> b;
            map[a][b] = 1;
        } 
        memset(vis, 0, sizeof(vis));
        path[0] = 1;
        vis[1] = 1;
        dfs(1);
    }
    return 0;
}

随后自己输入两个测试例子就发现了问题
用例1： （发现dfs判断时，k可以等于m，修改）
2 2
1 2
2 1
用例2： （发现main里输入的是n条边的信息，原来写成了m）
3 2
1 2
2 3

改了这两处就AC了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 15;

int n, m;
int vis[N];
int path[N];
int map[N][N];

void dfs(int k){ //从第一个点开始找周围最短的边 
    if(path[k-1] == m && k <= m){
        for(int i = 0; i < k-1; i++){
            printf("%d ", path[i]);
        }
        printf("%d\n", path[k-1]);
    }

    if(k > m) return; 

    for(int i = 2; i <= m; i++){
        if(!vis[i] && map[path[k-1]][i] == 1){
            //printf("k = %d i = %d\n", k, i);
            path[k] = i;
            vis[i] = 1;
            dfs(k + 1);
            vis[i] = 0;
        }
    }
}

int main(){
    while(cin >> m >> n){
        int a, b;
        memset(map, 0, sizeof(map));

        for(int i = 1; i <= n; i++){
            cin >> a >> b;
            map[a][b] = 1;
        } 
        memset(vis, 0, sizeof(vis));
        path[0] = 1;
        vis[1] = 1;
        dfs(1);
    }
    return 0;
}