tarjan 全WA求调
查看原帖
tarjan 全WA求调
661199
zhang_jinghan楼主2024/7/17 22:36
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
struct Edge{
	int v,next;
}edge[100005];
int head[10005];
void add(int k,int u,int v){
	edge[k].v=v;
	edge[k].next=head[u];
	head[u]=k;
	return;
}
bool cmp(stack<int>a,stack<int>b){
	return a.top()<b.top();
}
int n,m;
bool flag[10005],instack[10005];
int dfn[10005],low[10005],tot;
stack<int>sta[10005];
int sta_tot=1;
void tarjan(int u){
	dfn[u]=++tot;
	low[u]=dfn[u];
	flag[u]=false;
	instack[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].next){
		if(flag[edge[i].v]){
			tarjan(edge[i].v);
			low[u]=min(low[u],low[edge[i].v]);
		}else{
			if(instack[edge[i].v]){
				low[u]=min(low[u],dfn[edge[i].v]);
			}else{
				low[u]=min(low[u],low[edge[i].v]);
			}
		}
	}
	sta[sta_tot].push(u);
	if(low[u]==dfn[u]){
		sta_tot++;
	}
	instack[u]=false;
	return;
}
int main(){
	memset(head,-1,sizeof(head));
	memset(flag,true,sizeof(flag));
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(u!=v){
			add(i,u,v);
		}
	}
	for(int i=1;i<=n;i++){
		if(flag[i]){
			tarjan(i);
		}
	}
	cout<<sta_tot-1<<endl;
	for(int i=1;i<sta_tot;i++){
		sort(sta+1,sta+sta_tot,cmp);
	}
	int ans[10005],ans_tot=0;
	for(int i=1;i<sta_tot;i++){
		ans_tot=0;
		while(! sta[i].empty()){
			ans[++ans_tot]=sta[i].top();
			sta[i].pop();
		}
		sort(ans+1,ans+1+ans_tot);
		for(int j=1;j<=ans_tot;j++){
			cout<<ans[j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}
2024/7/17 22:36
加载中...