25求调
查看原帖
25求调
757101
junee楼主2024/7/20 20:00
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector> 
using namespace std;
typedef long long LL;
const int N=5e5+10,M=2e6+10;
int h[N],e[M],ne[M],id[M],idx;
int n,m;
int tt,stk[N],in_stk[N];
int st[N],sum[N],id[N],cnt,sz[N];
vector<vector<int>>scc;
int x[N],y[N];
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],id[idx]=c,h[a]=idx++;
}
void dfs(int u,int f){
	st[u]=1;
	in_stk[u]=1;
	stk[++tt]=u;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==f)continue;
		j=id[i]^id[i^1]^u;
		if(!st[j]){
			dfs(j,u);
			sum[u]+=sum[j];
		}
		if(in_stk[j]){
			sum[u]++,sum[j]--;
		}
	}
	in_stk[u]=0;
	if(!sum[u]){
		vector<int>vec;
		while(1){
			int x=stk[tt--];
			vec.push_back(x);
			if(x==u)break;
		}
		scc.push_back(vec);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1,a,b;i<=m;i++){
		cin>>a>>b;
		add(a,b,i),add(b,a,i);
	}
	for(int i=1;i<=n;i++){
		if(!st[i]){
		    dfs(i,0);
		}
	}
	cout<<scc.size()<<'\n';
	for(int i=0;i<scc.size();i++){
		auto vec=scc[i];
		cout<<vec.size()<<' ';
		for(int j=0;j<vec.size();j++)cout<<vec[j]<<' ';
		cout<<'\n';
	}
	return 0;
}

记录

2024/7/20 20:00
加载中...