Cod sursa(job #488575)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 29 septembrie 2010 13:54:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;

const cha08 Input[] = "biconex.in";
const cha08 Output[] = "biconex.out";

const int32 Dim = 100001;

int32 N, M;
int32 lvn[Dim], stn[Dim];
stack < pair <int32, int32> > s;
vector <int32> v[Dim];
vector < vector <int32> > comp;

void MakeBC( int32 x, int32 y ) {

    int32 xx, yy;
    vector <int32> aux;

    do {

        xx = s.top().first;
        yy = s.top().second;
        s.pop();
        aux.push_back( xx );
        aux.push_back( yy );
    }
    while( xx != x || yy != y );

    comp.push_back( aux );
}

void DF( int32 nod, int32 tat, int32 lvl ) {

    vector <int32> :: iterator it;

    lvn[nod] = stn[nod] = lvl;
    for( it = v[nod].begin(); it != v[nod].end(); ++it ) {

        if( *it == tat )
            continue;

        if( lvn[*it] == -1 ) {

            s.push( make_pair( nod, *it ) );
            DF( *it, nod, lvl + 1 );
            stn[nod] = min( stn[nod], stn[*it] );

            if( stn[*it] >= lvn[nod] )
                MakeBC( nod, *it );
        }
        else
            stn[nod] = min( stn[nod], lvn[*it] );
    }
}

int32 main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int32 i, j, x, y;

    fin >> N >> M;
    while( M-- ) {

        fin >> x >> y;
        v[x].push_back( y );
        v[y].push_back( x );
    }

    memset( lvn, -1, sizeof( lvn ) );
    DF( 1, 0, 0 );

    fout << comp.size() << "\n";
    for( i = 0; i < (int32) comp.size(); ++i ) {

        sort( comp[i].begin(), comp[i].end() );
        comp[i].erase( unique( comp[i].begin(), comp[i].end() ), comp[i].end() );

        for( j = 0; j < (int32) comp[i].size(); ++j )
            fout << comp[i][j] << " ";
        fout << "\n";
    }


    fin.close();
    fout.close();

    return 0;
}