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;
}