求调 调吐了

P8436 【模板】边双连通分量

__XU__ @ 2024-07-20 14:11:26

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m;
int dfn[N],low[N];
struct node{
    int u,i;
};
int b[N];
int dcc[N];
int ans;
vector<int> Ans[N];
vector<node> e[N];
int dcnt;
void tanjan(int u,int in){
    dfn[u]=low[u]=++dcnt;
    for(auto k : e[u]){
        int v=k.u,i=k.i;
        if(!dfn[v]){
            tanjan(v,i);
            if(dfn[u]<low[v]){
                b[i]=b[i^1]=1;
            }
            low[u]=min(low[u],low[v]);
        }
        else{
            if(i!=(in^1)){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
}
bool vis[N];
void dfs(int u){
    Ans[ans].push_back(u);
    for(auto k : e[u]){
        int v=k.u,i=k.i;
        if(vis[v]||b[i]){
            continue;
        }
        vis[v]=true;
        dfs(v);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(u==v){
            continue;
        }
        e[u].push_back({v,i});
        e[v].push_back({u,i+1});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tanjan(i,0);
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            continue;
        }

        ans++;
        vis[i]=true;
        dfs(i);
    }
        cout<<ans<<'\n';
    for(int u=1;u<=ans;u++){
        cout<<Ans[u].size()<<' ';
        for(auto v : Ans[u]){
            cout<<v<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

|