12分·求助
查看原帖
12分·求助
439327
南瓜桐楼主2021/10/6 14:32
#include<iostream>
#define maxn 10001
#define maxm 100001 
using namespace std;
int m,n;
int arr[maxn][maxn];
int vst[maxn],d[maxn];
int t=0;
void dfsOne(int x){
	vst[x]=1;
	for(int i=1;i<=n;i++){
		if(!vst[i]&&arr[x][i])dfsOne(i);
	}
	t++;
	d[t]=x;
}
void dfsTwo(int x){
	vst[x]=t;
	for(int i=1;i<=n;i++){
		if(!vst&&arr[i][x]) dfsTwo(i);
	}
}
int main(){
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		arr[a][b]=1;
	}
	int i,t=0;
	for(i=1;i<=n;i++){
		if(!vst[i]) dfsOne(i);
	}
	for(int i=1;i<=n;i++){
		vst[i]=0;
	}
	int ans=0;  
	for(int i=n;i>=1;i--){
		if(!vst[d[i]]){
			ans++;
			dfsTwo(d[i]);
		}
	}
	cout<<ans;
	return 0;
}
//洛p2341 https://www.luogu.com.cn/problem/P2341 
2021/10/6 14:32
加载中...