AcWing 847. 图中点的层次
原题链接
简单
作者:
王小强
,
2021-01-26 12:00:54
,
所有人可见
,
阅读 288
寒假辅导班课后作业 (不能输在起跑线上!)
BFS Template
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, u, v;
int main() {
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> seen(n + 1);
// build the directed graph
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
}
queue<int> q{{1}};
seen[1] = 1; // mark as seen
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
int cur = q.front(); q.pop();
for (const auto& nxt : g[cur]) {
if (nxt == n) { // 算一个小的性能优化吧~~
cout << steps + 1 << endl;
return 0;
}
if (seen[nxt]++) continue;
q.emplace(nxt);
}
}
++steps;
}
cout << -1 << endl;
return 0;
}