大佬help,please.(玄关)
查看原帖
大佬help,please.(玄关)
1001880
zalzlz楼主2024/9/16 21:08

请问此代码错在那?


#include<bits/stdc++.h>
using namespace std;
inline 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;
}
struct Edge{
	int to,next;
}edge[50010],re_edge[50010];
int n,m,cnt,id[50010],id_time[50010],id_time_older[50010],cnt_dfs,top,size_ch[50010],_stack[50010],group[50050],cn,re_id[50010],re_cnt;
int flag[50010];
void add_edge(int x,int y){
	edge[++cnt].to=y;
	edge[cnt].next=id[x];
	id[x]=cnt;
}
void tarjan(int u){
	_stack[++top]=u;
	flag[u]=1;
	id_time[u]=id_time_older[u]=++cnt_dfs;
	for(int i=id[u];i;i=edge[i].next){
		if(!flag[edge[i].to]){
			tarjan(edge[i].to);
			id_time_older[u]=min(id_time_older[u],id_time_older[edge[i].to]);
		}else if(flag[edge[i].to]){
			id_time_older[u]=min(id_time_older[u],id_time[edge[i].to]);
		}
	}
	if(id_time_older[u]==id_time[u]){
		flag[u]=0;
		group[u]=++cn;
		size_ch[cn]++;
		while(u!=_stack[top]){
			flag[_stack[top]]=0;
			group[_stack[top--]]=cn;
			size_ch[cn]++;
		}
		top--;
	}
}
void rebuild(){
	for(int i=1;i<=n;++i){
		for(int j=id[i];j;j=edge[j].next){
			if(group[i]!=group[edge[j].to]){
				re_edge[++re_cnt].next=re_id[group[i]];
				re_edge[re_cnt].to=group[edge[j].to];
				re_id[group[i]]=re_cnt; 
			}
		}
	}
}
int found(){
	int res=0;
	for(int i=1;i<=cn;++i){
		if(!re_id[i]){
			if(res)return 0;
			else res=size_ch[i];
		}
	}
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
	}
	for(int i=1;i<=n;++i){
		if(!id_time[i])tarjan(i);
	}
	rebuild();
	cout<<found();
	return 0;
}

万分感谢 (^-^)

2024/9/16 21:08
加载中...