仅能过样例1和样例2求调

P8436 【模板】边双连通分量

Exusiaiii @ 2024-11-05 21:40:51

仅能过样例1和样例2,求调。

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
const int M=5e6+5;
int bri[N],dfn[N],low[N],n,m,p[N],edge_num,dcc[N],vis[N],cnt,u,v,head[N],tot;
vector<int>ans[M];
struct node{
    int from;
    int to;
    int next;
}edge[M];
void add(int from,int to){
    edge[++edge_num].next=head[from];
    edge[edge_num].to=to;
    edge[edge_num].from=from;
    head[from]=edge_num;
}
void tarjan(int x,int in_edge){
    dfn[x]=low[x]=++tot;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])   bri[i]=bri[i^1]=true;
        }
        else if(i!=(in_edge^1)){
            low[x]=min(low[x],dfn[y]);
        }
    }
}
void dfs(int x){
    vis[x]=1;
    ans[cnt].push_back(x);
    for(int i=head[x];i;i=edge[i].next){
        if(bri[i])  continue;
        int v=edge[i].to;
        if(!vis[v]){
            dfs(v);
        }
    }

}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,i);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            cnt++;
        }
    }
    cout<<cnt<<endl;
    for(int i=0;i<cnt;i++){
        cout<<ans[i].size()<<" ";
        for(int v:ans[i]){
            cout<<v<<" ";
        }
        cout<<endl;
    }
}

|