抽象代码 能AC此题
查看原帖
抽象代码 能AC此题
661448
封禁用户楼主2024/8/5 17:03
#include<bits/stdc++.h>
using namespace std;

#define int long long

int n,m;
int vis[10001];
int low[10001];
vector<int>e[10001];
int cnt;
int f;
inline void tarjan(int x,int father)
{		
	vis[x]=1;
	low[x]=++cnt;
	for(int i=0;i<e[x].size();i++)
	{		
		int po=e[x][i];		
		if(!vis[po])tarjan(po,x);	
		low[x] = min( low[x] , low[po]);
		if(low[x] - 1 == 0 && father!=0) vis[x] = 1 ,f=1;
	}
}
int x,y;
signed main()
{	
	//freopen("scc.in","r",stdin);
	//freopen("scc.out","w",stdout);		
	scanf("%lld%lld",&n,&m);	
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);
	}	
	for(int i=0;i<=n;i++)vis[0]=0;
	int tot=0;	
	for(int i=1;i<=n;i++){		
		if(!vis[i]){
			for(int j=0;j<=n;j++)low[j]=INT_MAX;
			cnt=0;	
			f=0;	
			tarjan(i,0);							
			if(f) tot++;					
		}	
	}	
	printf("%lld\n",tot);
}
2024/8/5 17:03
加载中...