52pts求调!!!!!
查看原帖
52pts求调!!!!!
739534
OI_StarGod楼主2024/3/13 21:22
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
int dfn[N], low[N], id;
int s[N], h;
int cnt = 0;
bool vis[N];
int tot = 1;
int head[N], to[N], Next[N];
int Size[N];
void add(int u, int v) {
	to[++tot] = v;
	Next[u] = head[u];
	head[u] = tot;
}
void tarjan(int u) {
	++id;
	dfn[u] = id;
	low[u] = id;
	s[++h] = u;
	vis[u] = 1;
	for (int i = head[u]; i; i = Next[i]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}else if (vis[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		int v;
		++cnt;
		while (v = s[h--]) {
			vis[v] = 0;
			++Size[cnt];
			if (u == v) {
				break;
			}
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	int ans = 0;
	for (int i = 1; i <= cnt; ++i) {
		if (Size[i] > 1) {
			++ans;
		}
	}
	cout << ans;
	return 0;
}

记录

2024/3/13 21:22
加载中...