50分求助!

P8436 【模板】边双连通分量

chenhaoqwq @ 2023-09-29 22:36:13

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=5e5+10;
int n,m,low[N],cnt,depth[N],vis[N];
stack<int> s; 
vector<int> g[N],ans[N];
void dfs(int u,int fa){
//  cout<<u<<' ';
    vis[u]=1;
    low[u]=depth[u]=depth[fa]+1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v!=fa){
            if(vis[v]) low[u]=min(low[u],depth[v]);
            else{
//              s.push(v);
                s.push(v),dfs(v,u);
                low[u]=min(low[u],low[v]);
            }
        }
    }
    if(low[u]==depth[u]){
        cnt++;
//      cout<<endl;
        while(!s.empty()){
            int tmp=s.top();
//          cout<<tmp<<' ';
            s.pop();
            ans[cnt].push_back(tmp);
            if(tmp==u) break;
        }
//      cout<<endl;
    }
}
int main(){
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            s.push(i);
            dfs(i,0);
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
        cout<<ans[i].size()<<' ';
        for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

|