题目：所有可到达路径

题目链接：

98. 所有可达路径 (kamacoder.com)

解题思路：

邻接矩阵，注意没有result == -1时候特判

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>result;
vector<int>path;
void dfs(vector<vector<int>>grid, int x, int n) {if (x == n) {result.push_back(path);return;}for (int i = 1; i <= n; i++) {if (grid[x][i] == 1) {path.push_back(i);dfs(grid, i, n);path.pop_back();}}
}
int main() {int n, m;cin >> n >> m;vector<vector<int>>grid(n + 1, vector<int>(n + 1, 0));while (m--) {int s, t;cin >> s >> t;grid[s][t] = 1;}path.push_back(1);dfs(grid, 1, n);if (result.size() == 0) cout << -1 << endl;for (int i = 0; i < result.size(); i++) {for (int j = 0; j < result[i].size() - 1; j++) {cout << result[i][j] << ' ';}cout << result[i][result[i].size() - 1]<<endl;}
}

邻接表的写法：

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>result;
vector<int>path;
void dfs(vector<list<int>>grid, int x, int n) {if (x == n) {result.push_back(path);return;}for (auto i : grid[x]) {path.push_back(i);dfs(grid, i, n);path.pop_back();}
}
int main() {int n, m;cin >> n >> m;vector<list<int>>grid(n + 1);while (m--) {int s, t;cin >> s >> t;grid[s].push_back(t);}path.push_back(1);dfs(grid, 1, n);if (result.size() == 0) {cout << -1 << endl;}for (auto path : result) {for (int i = 0; i < path.size() - 1; i++) {cout << path[i] << ' ';}cout << path[path.size() - 1] << endl;}return 0;
}