P8435 【模板】点双连通分量

P8435 【模板】点双连通分量

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int M=4e6+6;

int h[N],ne[M],e[M],tot;
void add(int from,int to) {
    e[++tot]=to;
    ne[tot]=h[from];
    h[from]=tot;
}

int dfn[N],low[N],cnt;
int id[N],scnt;
stack<int>st;

vector<int>ans[N];

void tarjan(int now,int fa) {
    int son=0;
    dfn[now]=low[now]=++cnt;
    st.push(now);
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(dfn[to]==0) {
            son++;
            tarjan(to,now);
            low[now]=min(low[now],low[to]);
            if(low[to]>=dfn[now]) {
                scnt++;
                while(1) {
                    int k=st.top();
                    st.pop();
                    ans[scnt].push_back(k);
                    if(k==to)break;
                }
                ans[scnt].push_back(now);
            }
        }
        else if(to!=fa)low[now]=min(low[now],dfn[to]);
    }
    if(fa==0&&son==0)ans[++scnt].push_back(now);
}

int main() {
    int n,m;
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(dfn[i]==0) {
            while(st.size())st.pop();
            tarjan(i,0);
        }
    cout<<scnt<<endl;
    for(int i=1;i<=scnt;i++) {
        cout<<ans[i].size()<<' ';
        for(auto x:ans[i])cout<<x<<' ';
        cout<<endl;
    }
    return 0;
}