代码随想录leetcode200题之图论

1 介绍

本博客用来记录代码随想录leetcode200题之图论相关题目。

2 训练

题目1：98. 所有可达路径

解题思路：有向图，dfs(fa, node)。

C++代码如下，

#include <bits/stdc++.h>using namespace std;int n, m;
unordered_map<int,vector<int>> g;
vector<int> cur;
bool has_path = false;void dfs(int fa, int node) {if (!cur.empty() && cur.back() == n) {has_path = true;for (int i = 0; i+1 < cur.size(); ++i) cout << cur[i] << " ";cout << cur.back() << endl;return;}for (auto x : g[node]) {if (x != fa) {cur.emplace_back(x);dfs(node, x);cur.pop_back();}}return;
}int main() {g.clear();cur.clear();    cin >> n >> m;for (int i = 1; i <= m; ++i) {int a, b;cin >> a >> b;g[a].emplace_back(b);}cur.emplace_back(1);dfs(-1, 1);if (has_path == false) cout << "-1" << endl;return 0;
}

python3代码如下，

3 参考

代码随想录官网