Tarjan 0 pts 求调

红绿相间

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m;
int cxt,h[N];
struct node {int v,nxt;}a[N];
inline void add(int u,int v) {
    a[++cxt].v=v,
    a[cxt].nxt=h[u],
    h[u]=cxt;
}
int t[N];
int cnt,dfn[N],low[N];
void tarjan(int u,int edge) {
    dfn[u]=++cnt,low[u]=cnt;
    for(int l=h[u];l;l=a[l].nxt) {
        int i=a[l].v;
        if(!dfn[i]) {
            tarjan(i,l);
            low[u]=min(low[u],low[i]);
            if(dfn[u]<low[i])   t[l]=t[l^1]=1;
        }// edge^1: u所在边的另一端点的边
        else if(l!=(edge^1))   low[u]=min(low[u],dfn[i]);
    }
}
int anss,vis[N];
vector<int> ans[N];
void dfs(int u) {
    vis[u]=1;
    ans[anss].push_back(u);
    for(int l=h[u];l;l=a[l].nxt) {
        int i=a[l].v;
        if(!vis[i]&&!t[i])  dfs(i);
    }
}
signed main() {
    cin>>n>>m;
    for(int i=1;i<=m;++i) {
        int u,v;
        cin>>u>>v;
        if(u==v)    continue;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;++i)
        if(!vis[i]) ++anss,dfs(i);
    cout<<anss<<'\n';
    for(int i=1;i<=anss;++i) {
        cout<<ans[i].size()<<' ';
        for(int j:ans[i])   cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}