qwq___qaq @ 2023-04-01 11:14:44
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
int n,m,tot,u[maxn],v[maxn],dfn[maxn],low[maxn],fa[maxn];
inline int Make(int n){
for(int i=1;i<=n;++i)
fa[i]=i;
}
int Find(int x){
return fa[x]=(x==fa[x]?x:Find(fa[x]));
}
bool flg[maxn];
struct edge{
int to,id;
};
vector<edge> G[maxn];
vector<int> g[maxn];
void Tarjan(int u,int fa){
low[u]=dfn[u]=++tot;
for(auto N:G[u]){
int v=N.to,id=N.id;
if(v==fa)
continue;
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])
flg[id]=1;
} else if(v!=fa)
low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&u[i],&v[i]);
G[u[i]].push_back(edge({v[i],i}));
G[v[i]].push_back(edge({u[i],i}));
}
for(int i=1;i<=n;++i)
if(!dfn[i])
Tarjan(i,0);
Make(n);
for(int i=1;i<=m;++i)
if(!flg[i])
fa[Find(u[i])]=Find(v[i]);
int cnt=0;
for(int i=1;i<=n;++i){
cnt+=(fa[i]==i);
g[Find(i)].push_back(i);
}
printf("%d\n",cnt);
for(int i=1;i<=n;++i)
if(Find(i)==i){
printf("%d",int(g[i].size()));
for(auto v:g[i])
printf(" %d",v);
puts("");
}
return 0;
}
by liangbowen @ 2023-04-01 11:27:43
@UnnamedOrNamed 改 void Make(int n)
。
by Sprague_Garundy @ 2023-04-01 13:40:36
@UnnamedOrNamed 非 void
函数无返回值是 UB,开 O2 后就会 RE。