84pts求调,样例数据可以过
查看原帖
84pts求调,样例数据可以过
1223601
Parrott楼主2024/7/29 18:48
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[10010];
long long int vis[10100],_n,cnt,out[10010],siz[10010],tp,belong[10010],dfn[10010],low[10010],s[10010];
void tj(int u){
	cnt++;
	dfn[u]=cnt;
	low[u]=cnt;
	tp++;s[tp]=u;vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(dfn[v]==0){
			tj(v);
			low[u]=min(low[u],low[v]);
		    }
		else{
			if(vis[u]==1){
				low[u]=min(low[u],dfn[v]);
			}
		}
	}
	if(dfn[u]==low[u]){
		int t;
		++_n;
		do{
			t=s[tp];tp--;
			belong[t]=_n;
			vis[t]=0;
			++siz[_n];
		}while(t!=u);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tj(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int v=g[i][j];
			if(belong[i]!=belong[v])out[belong[i]]++;
		}
	}
	int ans,f=0;
	for(int i=1;i<=_n;i++){
		if(out[i]==0){
			f++;
			ans=i;
		}	
	}
	int t=0;
	if(f!=0){
		for(int j=1;j<=n;j++){
		    if(belong[j]==ans){
		    	t++;
			}
		}
		cout<<t<<endl;
	}
	return 0;
}
2024/7/29 18:48
加载中...