50分求助

P8436 【模板】边双连通分量

YQWQ @ 2023-08-15 17:31:03

#include <bits/stdc++.h>
using namespace std;

const int Kmaxb=2e6+5,Kmaxd=5e5+5;

struct E{
    int to,nex;
}e[Kmaxb*2];

int n,m,tot=1,head[Kmaxb];

void add(int x,int y){
    e[++tot].to=y,e[tot].nex=head[x],head[x]=tot;
}

int dn,dfn[Kmaxd],low[Kmaxd];
bool brg[Kmaxd];

void tarjan(int x, int in_edge) {
    dfn[x]=low[x]=++dn;
    for (int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if (!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if (low[y]>dfn[x]) brg[i]=brg[i^1]=true;
        }
        else if (i!=(in_edge^1)){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

int c[Kmaxd],sl=0;
vector <int> ans[Kmaxd];
void dfs(int x) {
    c[x] = sl;
    if(x) ans[sl].push_back(x); 
    for (int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if (c[y] || brg[i]) continue;
        dfs(y);
    }
}
int main(){
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;i++){
        if(!c[i]){
            sl++;
            dfs(i);
        }
    }
    cout<<sl<<endl;
    for(int i=1;i<=sl;i++){
        cout<<ans[i].size();
        for(int j=0;j<ans[i].size();j++){
            cout<<" "<<ans[i][j];
        }
        cout<<endl;
    }
}

|