Cod sursa(job #1785233)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 20 octombrie 2016 23:01:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

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

const int DIM = 1e5 + 5;
const int INF = 0x3f3f3f3f;

vector<int> ap, st, g[DIM]; vector< pair<int, int> > ce;
vector< vector<int> > bc; bitset<DIM> ma; int low[DIM], lev[DIM];

void dfs( int x, int f, int r ) {
    ma[x] = 1; st.push_back( x );
    low[x] = lev[x] = lev[f] + 1;

    int cnt = 0, z;
    for( auto y : g[x] ) {
        if( y == f )
            continue;

        if( ma[y] == 1 )
            low[x] = min( low[x], lev[y] );
        else {
            cnt ++;
            dfs( y, x, r );
            low[x] = min( low[x], low[y] );

            if( lev[x] < low[y] )
                ce.push_back( make_pair( x, y ) );

            if( lev[x] <= low[y] ) {
                bc.push_back( vector<int>(0) );

                do {
                    z = st.back(); st.pop_back();
                    bc[bc.size() - 1].push_back( z );
                } while( z != y );

                bc[bc.size() - 1].push_back(x);

                if( x != r && find( ap.begin(), ap.end(), x ) == ap.end() )
                    ap.push_back( x );
            }
        }
    }

    if( x == r && cnt >= 2 && find( ap.begin(), ap.end(), x ) == ap.end() )
        ap.push_back( x );

    return;
}

int main( int argc, const char *argv[] ) {

    int n, m; in >> n >> m;

    for( int i = 1; i <= m; i ++ ) {
        int x, y; in >> x >> y;
        g[x].push_back( y );
        g[y].push_back( x );
    }

    for( int i = 1; i <= n; i ++ )
        if( ma[i] == 0 ) dfs( i, 0, i );

    out << bc.size() << "\n";
    for( auto l : bc ) {
        for( auto x : l )
            out << x << " ";
        out << "\n";
    }

    return 0;
}