55
查看原帖
55
1069816
Tsuki091117楼主2024/7/10 16:50
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=5e5+10;
int idx,h[N],e[M],ne[M];
int ans,n,m,u,v;
int din[N];
int dfn[N],low[N],timestamp;
int in_stk[N],stk[N],top,scc_cnt;
void add(int a,int b){
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u,in_stk[u]=true;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(in_stk[j]){
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(low[u]==dfn[u]){
		int y;
		if(u!=stk[top]) ans++;
		do{
			y=stk[top--];
			in_stk[y]=0;
		}while(y!=u);
	}
}
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(u!=v){
			add(u,v);
			din[v]++;
		} 
	}
	for(int i=1;i<=n;i++){
		if(din[i]==0){
			ans++;
		}	
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}	
	cout<<ans-1;
	return 0;
}
2024/7/10 16:50
加载中...