Cod sursa(job #3226390)

Utilizator Victor_9Diaconescu Victor Victor_9 Data 21 aprilie 2024 12:09:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
//COMPONENTE BICONEXE ----------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 5;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, depth[nmax], low[nmax], viz[nmax];
vector < int > adj[nmax];

////////////////////////////////////////////////////////////////////////////////

void dfs_depth(int node){
    
    viz[node] = 1;
    
    for(auto elem : adj[node]){
        if(viz[elem] == 0){
            depth[elem] = depth[node] + 1;
            dfs_depth(elem);
        }
    }
    
}


void dfs_low(int node, int tata){
    
    low[node] = depth[node];
    
    for(auto elem : adj[node]){
        if(elem == tata || depth[elem] > depth[node]) continue;
        
        //muchie verde
        low[node] = min(low[node] , depth[elem]);
        
    }
    
    for(auto elem : adj[node]){
        
        if(elem == tata || depth[elem] != depth[node] + 1) continue;
        
        dfs_low(elem , node);
        
        low[node] = min(low[node] , low[elem]);
        
    }
    
}


stack < int > st;
vector < vector < int > > biconexe;
int cnt_cicluri;

void dfs_biconexe(int node, int tata){
    
    st.push(node);
    
    for(auto u : adj[node]){
        
        if(u == tata || depth[u] != depth[node] + 1) continue;
        
        dfs_biconexe(u , node);
        
        
        //am gasit o componenta conexa
        if(low[u] >= depth[node]){
            
            vector < int > comp_conexa;
            
            while(st.top() != u){
                comp_conexa.push_back(st.top());
                st.pop();
            }
            comp_conexa.push_back(u);
            comp_conexa.push_back(node);
            
            st.pop();
            
            biconexe.push_back(comp_conexa);
        }
        
    }
    
}



////////////////////////////////////////////////////////////////////////////////

int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0) , fout.tie(0);
    
    fin>>n>>m;
    
    for(int i=1;i<=m;i++){
        int x, y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    //depth --------------------------------------------------------------------
    depth[1] = 1;
    dfs_depth(1);
    
    //low-----------------------------------------------------------------------
    dfs_low(1  , 0);
    
    /*
    for(int i=1;i<=n;i++){
        cout<<low[i]<<" ";
    }
    cout<<"\n";
    */
    
    //componente biconexe ------------------------------------------------------
    dfs_biconexe(1 , 0);
    
    fout<<biconexe.size()<<"\n";
    for(auto elem : biconexe){
        for(auto u : elem){
            fout<<u<<" ";
        }
        fout<<"\n";
    }
    
    
}