P8436 【模板】边双连通分量

P8436 【模板】边双连通分量

//这个是看边和点，而不是看点和点
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int M=2e6+5;

int h[N],ne[M<<1],e[M<<1],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;
bool vis[N],bridge[M<<1];
int sum[N];
vector<int>ans[N];

void tarjan(int now,int E) {
    dfn[now]=low[now]=++cnt;
    st.push(now);
    vis[now]=1;
    for(int i=h[now];i!=-1;i=ne[i]) {
        int to=e[i];
        if(dfn[to]==0) {
            tarjan(to,i);
            low[now]=min(low[now],low[to]);
            //if(low[to]>dfn[now])
            //    bridge[i]=bridge[i^1]=1;
        }
        else if(i!=(1^E))
            low[now]=min(low[now],dfn[to]);
    }
    if(dfn[now]==low[now]) {
        scnt++;
        while(1) {
            int k=st.top();
            st.pop();
            vis[k]=0;
            id[k]=scnt;
            sum[id[k]]++;
            ans[id[k]].push_back(k);
            if(k==now)break;
        }
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    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)tarjan(i,-1);
    cout<<scnt<<endl;
    for(int i=1;i<=scnt;i++) {
        cout<<sum[i]<<' ';
        for(auto x:ans[i])cout<<x<<' ';
        cout<<endl;
    }
    return 0;
}