rt,SCC求调试
查看原帖
rt,SCC求调试
1061320
Isharmla楼主2023/10/13 17:10

求调试。

// Problem: B3609 [图论与代数结构 701] 强连通分量
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3609
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define F(i,a,b) for(int i=a;i<=b;i++)

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

const int N=4e5+5;

int head[N],nxt[N],to[N],tot;

inline void AddEdge(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
} 	
int cnt,n,m,stk[N],tp,number_scc,dfn[N],low[N];//栈元素,栈顶,SCC的数量
bool In_stk[N];//是否在栈里面
vector<int> S[N];
void Tarjan(int u){
	dfn[u]=low[u]=(++cnt);
	stk[++tp]=u;In_stk[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		if(!dfn[to[i]]){
			Tarjan(to[i]);
			low[u]=min(low[u],low[to[i]]);
		}else if(In_stk[to[i]]==1){
			low[u]=min(low[u],dfn[to[i]]);
		}
	}
	if(dfn[u]==low[u]){
		number_scc++;
		while(stk[tp]!=u){
			In_stk[tp]=0;
			S[number_scc].push_back(stk[tp]);
			tp--;
		}
		In_stk[tp]=0;
		S[number_scc].push_back(u);
		tp--;
	}
}
bool cmp(vector <int> a, vector <int> b) {
	return *a.begin() < *b.begin();
}
signed main(){
	n=read(),m=read();     
	for(int i=1,u,v;i<=m;i++){
		u=read(),v=read();
		AddEdge(u,v);
	}
	F(i,1,n){
		if(!dfn[i]) Tarjan(i);
	}
	for (int i=1;i<=number_scc;i++)
		sort(S[i].begin(),S[i].end());
	sort(S+1,S+1+number_scc,cmp);
	cout<<number_scc<<endl;
	F(i,1,number_scc){
		//sort(S[i].being(),S[i].end());
		F(j,0,S[i].size()-1) cout<<S[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}

2023/10/13 17:10
加载中...