求调 调吐了
查看原帖
求调 调吐了
1125054
__XU__楼主2024/7/20 14:11
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m;
int dfn[N],low[N];
struct node{
	int u,i;
};
int b[N];
int dcc[N];
int ans;
vector<int> Ans[N];
vector<node> e[N];
int dcnt;
void tanjan(int u,int in){
	dfn[u]=low[u]=++dcnt;
	for(auto k : e[u]){
		int v=k.u,i=k.i;
		if(!dfn[v]){
			tanjan(v,i);
			if(dfn[u]<low[v]){
				b[i]=b[i^1]=1;
			}
			low[u]=min(low[u],low[v]);
		}
		else{
			if(i!=(in^1)){
				low[u]=min(low[u],dfn[v]);
			}
		}
	}
}
bool vis[N];
void dfs(int u){
	Ans[ans].push_back(u);
	for(auto k : e[u]){
		int v=k.u,i=k.i;
		if(vis[v]||b[i]){
			continue;
		}
		vis[v]=true;
		dfs(v);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		if(u==v){
			continue;
		}
		e[u].push_back({v,i});
		e[v].push_back({u,i+1});
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tanjan(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]){
			continue;
		}
		
		ans++;
		vis[i]=true;
		dfs(i);
	}
		cout<<ans<<'\n';
	for(int u=1;u<=ans;u++){
		cout<<Ans[u].size()<<' ';
		for(auto v : Ans[u]){
			cout<<v<<' ';
		}
		cout<<'\n';
	}
	return 0;
}
2024/7/20 14:11
加载中...