myj128128 @ 2024-11-26 19:35:30
提供一个vector模拟map的写法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
int read(){
int m=0;int f=1;char c=getchar();
while((c<'0'||c>'9')){if(c=='-')f=-1;c=getchar();}
while(!(c<'0'||c>'9')){m=m*10+(c-'0');c=getchar();}
return m*f;
}
const int maxn=500050;
int n,m;
vector<int>vec[maxn];
int low[maxn];
int dfn[maxn];
int tot;
int ecc;
vector<bool>bridge[maxn];
vector<pii >mp[maxn];
void tarjan(int u,int fa){
low[u]=dfn[u]=++tot;
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i];
if(v==fa)continue ;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
ecc++;
// bridge.pb({min(u,v),max(u,v)});
bridge[u][i]=bridge[mp[u][i].first][mp[u][i].second]=1;
}
}else low[u]=min(low[u],dfn[v]);
}
}
int col[maxn];
vector<int >ans[maxn];
int cnt;
void dfs(int u){
col[u]=cnt;
ans[cnt].pb(u);
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i];
if(bridge[u][i]||col[v])continue ;
dfs(v);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
m=read();
for(int i=1;i<=m;i++){
int u;int v;
u=read();v=read();
vec[u].pb(v);
vec[v].pb(u);
bridge[u].pb(0);
bridge[v].pb(0);
// mp[{u,vec[u].size()-1}]={v,vec[v].size()-1};
// mp[{v,vec[v].size()-1}]={u,vec[u].size()-1};
mp[u].pb({v,vec[v].size()-1});
mp[v].pb({u,vec[u].size()-1});
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<vec[i].size();j++){
// int v=vec[i][j];
// if(mp[{i,v}])bridge[i][j]=1;
// }
// }
for(int i=1;i<=n;i++){
if(!col[i]){
++cnt;
dfs(i);
}
}
// for(int i=1;i<=cnt;i++)
// sort(ans[i].begin(),ans[i].end());
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++){
cout<<ans[i].size()<<' ';
for(int u:ans[i])cout<<u<<' ';
cout<<'\n';
}
return 0;
}