代码随想录训练营第55天|深度优先搜索

98. 所有可达路径

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<vector<int>>& graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i : graph[x]) { // 找到 x指向的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}
}int main() {int n, m, s, t;cin >> n >> m;vector<vector<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}path.push_back(1); dfs(graph, 1, n); // 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa.back()  << endl;}
}

用邻接表存储图结构，搜索路径采用dfs，其实就是回溯模板。