Cod sursa(job #3226765)

Utilizator Ana_22Ana Petcu Ana_22 Data 22 aprilie 2024 19:13:29
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001

using namespace std;

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

int n, m, no_comp, timp;
vector <int> edges[NMAX];
int dfn[NMAX], low[NMAX], art[NMAX], viz[NMAX];
vector<int> cbc[NMAX];
stack <int> st;

void biconex( int node, int parent ) {
    dfn[node] = low[node] = ++timp;
    st.push( node );
    for( unsigned int i = 0; i < edges[node].size(); i++ ) {
        int newnode = edges[node][i];
        
        if( dfn[newnode] == -1 ) {
            biconex( newnode, node );
            low[node] = min( low[node], low[newnode] );
            
            // if( low[newnode] > dfn[node], at (newnode, node) e punte
            if( low[newnode] >= dfn[node] ) {
                art[node] = 1;
                no_comp++;
                
                cbc[no_comp].push_back( node );
                while( !st.empty() && st.top() != newnode ) {
                    cbc[no_comp].push_back( st.top() );
                    st.pop();
                }
                if( !st.empty() && st.top() == newnode ) {
                    cbc[no_comp].push_back( st.top() );
                    st.pop();
                }
            }
        }
        else {
            if( newnode != parent )
                low[node] = min( low[node], dfn[newnode] );
        }
        
    }
}

int main() {
    int x, y;
    fin >> n >> m;
    for( int i = 0; i < m; i++ ) {
        fin >> x >> y;
        edges[x].push_back( y );
        edges[y].push_back( x );
    }
    for( int i = 0; i <= n; i++ )
        dfn[i] = low[i] = -1;
    biconex( 1, 0 );
    fout << no_comp << '\n';
    for( int i = 1; i <= no_comp; i++ ) {
        for( unsigned int j = 0; j < cbc[i].size(); j++ )
            fout << cbc[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}