建议加强数据
查看原帖
建议加强数据
933604
LYBT楼主2025/8/1 12:24

rt,我 tarjan 板子都错了,依然AC。
如下第 2222 行,ins[v] 写成了 ins[u]

#include <bits/stdc++.h>
using namespace std;
const int M = 5e4 + 5;
const int N = 1e4 + 5;
int n, m;
vector<int> e[N];
int dfn[N], low[N], tim, Stack[N], top, belong[N], siz[N], fu[M], fv[M], dout[N];
bool ins[N];
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tim;
	Stack[++top] = u;
	ins[u] = 1;
	for(int v : e[u]) {
		if(!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			
		}
		else if(ins[u]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		while(Stack[top + 1] != u) {
			siz[u]++;
			belong[Stack[top]] = u;
			ins[Stack[top--]] = 0;
		}
	}
}
void shrink_node() {
	for(int i = 1; i <= m; ++i) {
		int du = belong[fu[i]], dv = belong[fv[i]];
		if(du != dv)
			dout[du]++;
	}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		cin >> fu[i] >> fv[i];
		e[fu[i]].push_back(fv[i]);
	}
	for(int i = 1; i <= n; ++i) {
		if(!dfn[i]) {
			top = 0;
			tarjan(i, 0);
		}
	}
	shrink_node();
	int cnt = 0, ans;
	for(int i = 1; i <= n; ++i) {
		if(dout[i] == 0 && belong[i] == i) {
			cnt++;
			ans = siz[i];
		}
	}
	if(cnt == 1) cout << ans;
	else cout << 0;
	return 0;
}
2025/8/1 12:24
加载中...