Cod sursa(job #3298527)

Utilizator OvidRata Ovidiu Ovid Data 30 mai 2025 21:27:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.56 kb
#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


string numeFisier="biconex";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout

#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll






class BiconexComponents{
    
    public: 
        
        int n, m;
        vector<vector<int>> g;
        vector<int> depth;
        vector<int> lowpoint;
        vector<bool> ver;
         
        void getNM(int N, int M){
            n=N, m=M;
            g.assign(n+5, {});
            depth.assign(n+5, 0);
            lowpoint.assign(n+5, 0);
            ver.assign(n+5, 0);
        }

        vector<vector<int>> biconnectedComponents; 
        vector<bool> verNode;
        vector<vector<int>> edgeStack;

        void dfs(int u){

            lowpoint[u]=depth[u];
            
            ver[u]=true;
            
            for(int v:g[u]){
                
                if( !ver[v] ){
                    
                    depth[v] = depth[u]+1;
                    
                    edgeStack.pb({u,v});
                    dfs(v);

                    lowpoint[u]=min(lowpoint[u], lowpoint[v]);


                    if( lowpoint[v]>=depth[u] || (u==1 && g[u].size()>1) ){
                        //cout<<u<<"++"<<edgeStack.size()<<"+++++=\n";
                        biconnectedComponents.pb({});
                        verNode[u] = true;
                        verNode[v] = true;
                        biconnectedComponents.back().pb(u);
                        biconnectedComponents.back().pb(v);
                        for(int j=((int)edgeStack.size())-1; j>=0 && edgeStack[j]!=((vector<int>){u,v}); j--){
                            for(int k=0; k<2; k++){
                                int nk = edgeStack[j][k];
                                if(!verNode[nk]){
                                    biconnectedComponents.back().pb(nk);
                                    verNode[nk]=true;
                                }
                            }
                        }


                        verNode[u] = false;
                        verNode[v] = false;
                        // biconnectedComponents.back().pb(u);
                        // biconnectedComponents.back().pb(v);
                        for(int j=((int)edgeStack.size())-1; j>=0 && edgeStack[j]!=((vector<int>){u,v}); j--){
                            for(int k=0; k<2; k++){
                                int nk = edgeStack[j][k];
                                if(!verNode[nk]){
                                    // biconnectedComponents.back().pb(nk);
                                    verNode[nk]=false;
                                }
                            }
                            //cout<<edgeStack.back()[0]<<" "<<edgeStack.back()[1]<<"---\n";
                            edgeStack.pop_back();
                        }
                        //cout<<edgeStack.back()[0]<<" "<<edgeStack.back()[1]<<"---\n";
                        edgeStack.pop_back();
                        
                    }




                }
                else{
                    lowpoint[u]=min(lowpoint[u], depth[v]);
                }

                
            }


        }

        void buildBiconnectedComponents(){
            if( !biconnectedComponents.empty() ){
                return;
            }
            verNode.assign(n+5, 0);
            dfs(1);
        }

} bcc;




void input(){
    
    cin>>bcc.n>>bcc.m;
    bcc.getNM(bcc.n,bcc.m);
    
    for(int i=1,u,v; i<=bcc.m; i++){
        cin>>u>>v;
        bcc.g[u].pb(v);
        bcc.g[v].pb(u);
    }



}


void solve(){
    bcc.buildBiconnectedComponents();
    // cout<<bcc.n<<"---\n";
    // for(int i=1; i<=bcc.n; i++){
    //     cout<<bcc.ver[i]<<" --\n";
    // }
}


void output(){
    cout<<bcc.biconnectedComponents.size()<<"\n";
    for(auto component: bcc.biconnectedComponents){
        for(auto u : component){
            cout<<u<<" ";
        }
        cout<<"\n";
    }
}

int32_t main(){
    INIT

    input();

    solve();

    output();


    return 0;
}