abc376D Cycle
有N个顶点M条边的简单有向图，求包含1号点的最小环的顶点数，如果不存在，输出-1。
2<=N<=2E5, 1<=M<=2E5
分析：bfs求最小环。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int N, M;
std::cin >> N >> M;
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
}
int ans = N + 1;
std::vector<int> dis(N, -1);
std::queue<int> q;
q.push(0);
dis[0] = 0;
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto x : adj[t]) {
if (x == 0) {
ans = std::min(ans, dis[t] + 1);
}
if (dis[x] == -1) {
dis[x] = dis[t] + 1;
q.push(x);
}
}
}
if (ans > N) {
ans = -1;
}
std::cout << ans << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}