图论路径查找输出所有路径

Question

路径查找
题目描述

在广阔的大陆上有 n 个城市（编号为 11 ~ nn），城市之间修建了 m 条双向的道路，且任意两个城市之间最多只有 1 条路。

请编程输出，从 1 号城市到 n 号城市的所有可行的路线，为了节约时间，每条路线都不会重复的经过同一个点。

请按字典码从小到大的顺序，输出每一条道路，如果道路数量超过 1000 条，你只需要输出前 1000 条道路。
输入

第 1 行，有 2 个整数 n 和 m。（1≤n≤100,1≤m≤(n−1)×n/2）

接下来 mm 行，每行有 2 个整数 x 和 y，表示两个城市之间有一条双向道路。（1≤x,y≤n，x≠y，两个城市之间至多只有一条双向道路）
输出

输出从 1 号城市到 n 号城市的所有路线，按照字典码从小到大的顺序输出，每行输出 1 条路线，路线数超过 1000 条，只需要输出前 1000条；本题的测试数据保证从 1 号城市到 n号城市，至少存在一条可以走到的路径。
样例
输入

5 7
1 2
1 3
2 3
3 4
2 5
4 5
3 5

输出

1 2 3 4 5
1 2 3 5
1 2 5
1 3 2 5
1 3 4 5
1 3 5

提交时间：2023-02-04 20:00:49

运行 ID: 3103964

#include<bits/stdc++.h>
using namespace std;
int a[11][11],n,e;
bool f[11];
void dfs(int x){
    f[x]=true;
    cout<<x<<" ";
    for(int i=1;i<=n;i++){
        if(!f[i]&&a[x][i]){
            dfs(i);
        }
    }
}
int main(){
    cin>>n>>e;
    for(int i=1;i<=e;i++){
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
        a[y][x]=1;
    }
    dfs(1);
    return 0;
}

怎么改

Answer 1

该回答引用ChatGPT
请参考下面 方法，如果可行，还请点击 采纳 ，感谢！
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000010;
vector<int> g[N];
int n, m, tot, cnt = 0, vis[N];
void bfs(int s, int e) {
    queue<vector<int> > q;
    vector<int> v(1, s);
    q.push(v);
    while (q.size() && cnt <= 1000) {
        vector<int> u = q.front();
        q.pop();
        int t = u[u.size()-1];
        if (t == e) {
            for (int i = 0; i < u.size(); i++)
                cout << u[i] << " ";
            cout << endl;
            cnt++;
        }
        for (int i = 0; i < g[t].size(); i++) {
            int v = g[t][i];
            if (!vis[v]) {
                vis[v] = 1;
                vector<int> w = u;
                w.push_back(v);
                q.push(w);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1, n);
    return 0;
}