算法训练营day50(12.18)

题目: 98. 所有可达路径
代码:

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<bool>>& graph, int start, int end, vector<int>& cur, vector<vector<int>>& result) {
    if(start == end) {
        result.push_back(cur);
        return;
    }
    
    for(int i = 1; i <= end; i++) {
        if(graph[start][i]) {
            cur.push_back(i);
            dfs(graph, i, end, cur, result);
            cur.pop_back();
        }
    }
}

int main(void) {
    int m, n;
    cin >> n >> m;
    vector<vector<bool>> graph(n + 1, vector<bool>(n + 1));
    
    while(m--) {
        int x, y;
        cin >> x >> y;
        graph[x][y] = true;
    }
    
    vector<vector<int>> result;
    vector<int> path;
    path.push_back(1);
    dfs(graph, 1, n, path, result);
    
    if(result.size() == 0) {
        cout << -1 << endl;
        return 0;
    }
    for(int i = 0; i < result.size(); i++) {
        for(int j = 0; j < result[i].size(); j++) {
            if(j > 0) {
                cout << " ";
            }
            cout << result[i][j];
        }
        cout << endl;
    }
    
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容