算法分析
$\operatorname{dfs}$ 和 $\operatorname{bfs}$ 的板题
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
rep(v, n) sort(to[v].begin(), to[v].end());
{
vector<bool> used(n);
auto dfs = [&](auto f, int v) -> void {
cout << v+1 << ' ';
used[v] = true;
for (int u : to[v]) {
if (used[u]) continue;
f(f, u);
}
};
dfs(dfs, 0);
puts("");
}
{
const int INF = 1001001001;
vector<int> dist(n, INF);
queue<int> q;
dist[0] = 0; q.push(0);
while (q.size()) {
int v = q.front(); q.pop();
cout << v+1 << ' ';
for (int u : to[v]) {
if (dist[u] != INF) continue;
dist[u] = dist[v]+1;
q.push(u);
}
}
}
return 0;
}