为何MLE
查看原帖
为何MLE
713826
EDJIW楼主2025/6/19 12:28
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=5e4+50;
ll n,m,idx,siz[N],tp,st[N],be[N],ans;
bool vis[N];
struct Node{
	ll to[N],nex[N],la[N],mcnt=1;
	void add(ll u,ll v){
		mcnt++;to[mcnt]=v,nex[mcnt]=la[u];la[u]=mcnt;
	}
}a,b;

void dfs1(ll x){
	vis[x]=1;
	for(ll i=a.la[x];i;i=a.nex[i])if(!vis[a.to[i]])dfs1(a.to[i]);
	st[++tp]=x;
}

void dfs2(ll x,ll tot){
	vis[x]=1,siz[tot]++,be[x]=tot;
	for(ll i=b.la[x];i;i=b.nex[i])if(!vis[b.to[i]])dfs2(b.to[x],tot);
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1,u,v;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		a.add(u,v);b.add(v,u);
	}
	
	for(ll i=1;i<=n;i++)if(!vis[i])dfs1(i);
	memset(vis,0,sizeof(vis));
	while(tp){
		ll u=st[tp--];
		if(!vis[u])dfs2(u,++idx);
	}
	
	for(ll i=1;i<=idx;i++)ans+=siz[i]>1;
	printf("%lld",ans);
	
	return 0;
}
2025/6/19 12:28
加载中...