神奇的小错误求助!!!
查看原帖
神奇的小错误求助!!!
143742
Nelson_Wang楼主2021/9/24 18:18

WA了第6、10、11、12四个点

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
const int M = 5e4+10;

int n, m, f[N];
int dfn[N], low[N], col[N], cnt, tot;
int e[M], nex[M], hed[N], ct;
vector<int> to[N];
stack<int> sta;

void tarjan(int x){
	low[x] = dfn[x] = ++cnt;
	sta.push(x);
	for(int i=hed[x]; i; i=nex[i]){
		if(!dfn[e[i]])
			tarjan(e[i]);
		if(dfn[e[i]])
			low[x] = min(low[x], low[e[i]]);
	}
	if(low[x]==dfn[x]){
		col[x] = ++tot;
		while(sta.top()!=x){
			col[sta.top()] = tot;
			sta.pop();
		}
		sta.pop();
	}
}
void dfs(int x){
	f[x] += 1;
	for(int i:to[x]){
		if(!f[i])
			dfs(i);
		f[i] += f[x];
	}
}
int main(){
	// freopen("input.txt", "r", stdin);
	scanf("%d%d", &n, &m);
	while(m--){
		int a, b;
		scanf("%d%d", &a, &b);
		e[++ct] = b, nex[ct] = hed[a], hed[a] = ct;
	}
	for(int i=1; i<=n; ++i)
		if(!dfn[i])
			tarjan(i);
	for(int i=1; i<=n; ++i)
		for(int j=hed[i]; j; j=nex[j]){
			if(col[i]==col[e[j]])
				continue;
			to[col[i]].push_back(col[e[j]]);
		}
	for(int i=1; i<=tot; ++i)
		if(!f[i])
			dfs(i);
	int ans = 0;
	for(int i=1; i<=tot; ++i)
		if(f[i]==tot){
			for(int j=1; j<=n; ++j)
				if(col[j]==i)
					++ans;
			break;
		}
	printf("%d", ans);
	return 0;
}
2021/9/24 18:18
加载中...