WA 88分 求救
查看原帖
WA 88分 求救
367521
roger_yrj楼主2022/8/26 14:58
#include<bits/stdc++.h>
using namespace std;
int n,m,tcnt,dfn[10010],low[10010],belong[10010],_n,s,p,ans,siz[10010];
bool vis[10010];
vector<int>e[10010],_e[10010];
stack<int>sta;
void tarjan(int u){
	dfn[u]=low[u]=++tcnt;
	sta.push(u);
	for(int i=0,len=e[u].size();i<len;i++){
		int v=e[u][i];
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(!belong[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		_n++;
		while(sta.top()!=u){
			int v=sta.top();
			siz[_n]++;
			belong[v]=_n;
			sta.pop();
		}
		siz[_n]++;
		belong[u]=_n;
		sta.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int u=1;u<=n;u++){
		for(int i=0,len=e[u].size();i<len;i++){
			int v=e[u][i];
			if(belong[u]!=belong[v]){
				vis[belong[u]]=1;
			}
		}
	}
	for(int i=1;i<=_n;i++){
		if(!vis[i])ans+=siz[i];
	} 
	cout<<ans;
}

#3 #4 #13 WA

2022/8/26 14:58
加载中...