50pts悬关求救
查看原帖
50pts悬关求救
1198194
zlqwq楼主2024/12/15 13:46
#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int n,m,idx;
const int MAXN=5e6+5;
vector<int> z[MAXN];
int low[MAXN],dfn[MAXN];
vector<vector<int> > ans;
stack<int> stk;
bool vis[MAXN];
void tarjan(int u,int fa){
	stk.push(u);
	vis[u]=1;
	low[u]=dfn[u]=++idx;
	for(auto v:z[u]){
		if(v==fa){
			continue;	
		}
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		vector<int> vec;
		vec.push_back(u);
		while(stk.top()!=u){
			vec.push_back(stk.top());
			vis[stk.top()]=0;
			stk.pop();
		}
		stk.pop();
		ans.push_back(vec);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		z[u].push_back(v);
		z[v].push_back(u);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i,i);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i=0;i<ans.size();++i){
		cout<<ans[i].size()<<" ";
		for(int j=0;j<ans[i].size();++j){
			cout<<ans[i][j]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}
2024/12/15 13:46
加载中...