tarjan 56分RE求助
查看原帖
tarjan 56分RE求助
352426
就决定是你辣楼主2022/8/28 15:45

数组已开到原范围20倍,但仍有RE和WA的情况!大佬查错希望TAT

#include<bits/stdc++.h>

using namespace std;
int head[200005],nxt[1000005],to[1000005],cnt,tot,n,m,top,idx,siz[200005];
void add(int u,int v){
	nxt[++tot]=head[u];to[head[u]=tot]=v;
}
int dfn[200005],low[200005],st[200005],ins[200005],mmp[200005],du[200005];
void dfs(int u){
	low[u]=dfn[u]=++cnt;
	ins[st[++top]=u]=1;
	for(int i=head[u];i;i=nxt[i]){
		
		if(!dfn[to[i]]){
			dfs(to[i]);
			low[u]=min(low[u],low[to[i]]);
		}else if(ins[to[i]]){
			low[u]=min(low[u],dfn[to[i]]);
		}
	}
	if(low[u]==dfn[u]){
		int v;++idx;
		do{
			ins[v]=0;
			++siz[idx];
			v=st[top--];
			mmp[v]=idx;
		}while(v!=u);
		
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])dfs(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nxt[j]){
			int v=to[i];
			if(mmp[i]!=mmp[v]){
				du[mmp[i]]++;
			}
		}
	}
	int tot1=0;
	for(int i=1;i<=idx;++i){
		if(!du[i]){
			if(tot1){
				cout<<0;
				return 0;
			}
			else {
				tot1=i;
				
			}
		}
	}
	cout<<siz[tot1]<<endl;
}
2022/8/28 15:45
加载中...