50分求助!
查看原帖
50分求助!
696748
youakioi楼主2023/9/29 22:36
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=5e5+10;
int n,m,low[N],cnt,depth[N],vis[N];
stack<int> s; 
vector<int> g[N],ans[N];
void dfs(int u,int fa){
//	cout<<u<<' ';
	vis[u]=1;
	low[u]=depth[u]=depth[fa]+1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v!=fa){
			if(vis[v]) low[u]=min(low[u],depth[v]);
			else{
//				s.push(v);
				s.push(v),dfs(v,u);
				low[u]=min(low[u],low[v]);
			}
		}
	}
	if(low[u]==depth[u]){
		cnt++;
//		cout<<endl;
		while(!s.empty()){
			int tmp=s.top();
//			cout<<tmp<<' ';
			s.pop();
			ans[cnt].push_back(tmp);
			if(tmp==u) break;
		}
//		cout<<endl;
	}
}
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			s.push(i);
			dfs(i,0);
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++){
		cout<<ans[i].size()<<' ';
		for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<' ';
		cout<<endl;
	}
	return 0;
}


2023/9/29 22:36
加载中...