tarjan写法wa一个点,求调
查看原帖
tarjan写法wa一个点,求调
537458
struct_cym楼主2023/10/13 18:12
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
vector<int>edge[N];
int dfn[N],low[N];
int st[N];//栈
int co[N]; 
int flag[N];
int num,tops,col;
void tarjan(int u){
	dfn[u]=low[u]=num++;
	st[++tops]=u;
	for(int i=0;i<edge[u].size();i++){
		int v=edge[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!co[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		co[u]=++col;
		while(st[tops]!=u){
			co[st[tops]]=col;
			--tops;
		}
		--tops;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	cout<<col<<endl;
	for(int i=1;i<=n;i++){
		if(flag[i]){
			continue;
		}
		flag[i]=1;
		cout<<i<<" ";
		for(int j=i+1;j<=n;j++){
			if(co[j]==co[i]){
				flag[j]=1;
				cout<<j<<" ";
			}
		}
		cout<<endl;
	}
	return 0;
}
2023/10/13 18:12
加载中...