Exusiaiii @ 2024-11-05 21:40:51
仅能过样例1和样例2,求调。
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
const int M=5e6+5;
int bri[N],dfn[N],low[N],n,m,p[N],edge_num,dcc[N],vis[N],cnt,u,v,head[N],tot;
vector<int>ans[M];
struct node{
int from;
int to;
int next;
}edge[M];
void add(int from,int to){
edge[++edge_num].next=head[from];
edge[edge_num].to=to;
edge[edge_num].from=from;
head[from]=edge_num;
}
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++tot;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]) bri[i]=bri[i^1]=true;
}
else if(i!=(in_edge^1)){
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(int x){
vis[x]=1;
ans[cnt].push_back(x);
for(int i=head[x];i;i=edge[i].next){
if(bri[i]) continue;
int v=edge[i].to;
if(!vis[v]){
dfs(v);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,i);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
cnt++;
}
}
cout<<cnt<<endl;
for(int i=0;i<cnt;i++){
cout<<ans[i].size()<<" ";
for(int v:ans[i]){
cout<<v<<" ";
}
cout<<endl;
}
}