25pts求调
查看原帖
25pts求调
1351669
yangruixi0728楼主2025/2/6 01:18
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=500010;
typedef long long LL;
int h[N],e[M],ne[M],idx;
int n,m;
int low[N],dfn[N],timestamp;
int scc_cnt,id[N],Size[N];
bool in_stk[N];
int stk[N],top,dout[N],din[N];
inline void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
	low[u]=dfn[u]=++timestamp;
	stk[++top]=u;
	in_stk[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in_stk[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int y;
		++scc_cnt;
		do{
			y=stk[top--];
			in_stk[y]=0;
			id[y]=scc_cnt;
		}while(y!=u);
	}
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main(){
    n=read(),m=read();
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add(u,v);
    }
    for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++){
	    for(int j=h[i];~j;j=ne[j]){
	        int k=e[j];
	        int a=id[i],b=id[k];
	        if(a!=b){
	            din[a]++;
	        }
	    }
	}
	int cnt=0;
	for(int i=1;i<=scc_cnt;i++){
		if(!din[i]) cnt++;
	}
	cout<<cnt;
    return 0;
}
2025/2/6 01:18
加载中...