Cod sursa(job #1758063)

Utilizator BLz0rDospra Cristian BLz0r Data 16 septembrie 2016 13:45:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define Nmax 100002

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

int N, M, ind = 1, NrComp;
int Index[Nmax], LowLink[Nmax];
vector < int > G[Nmax], Comp[Nmax];
stack < pair < int, int > > St;

void GetComp( int nod1, int nod2 ){

    NrComp++;
    int x1, x2;

    do{
        x1 = St.top().first;
        x2 = St.top().second;
        St.pop();

        Comp[NrComp].push_back(x1);
        Comp[NrComp].push_back(x2);

    }while( make_pair( nod1, nod2 ) != make_pair( x1, x2 ) );

}

void DFS( int nod ){

    vector < int > :: iterator it;

    Index[nod] = LowLink[nod] = ind++;

    for( it = G[nod].begin(); it != G[nod].end(); ++it ){

        if( !Index[*it] ){

            St.push( make_pair( nod, *it ) );

            DFS(*it);
            LowLink[nod] = min( LowLink[nod], LowLink[*it] );

            if( LowLink[*it] >= Index[nod] )
                GetComp( nod, *it );
        }
        else
            LowLink[nod] = min( LowLink[nod], Index[*it] );
    }
}

int main(){

    fin >> N >> M;

    int x, y;
    while( M-- ){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for( int i = 1; i <= N; ++i )
        if( !Index[i] )
            DFS(i);

    vector < int > :: iterator it;

    fout << NrComp << "\n";
    for( int i = 1; i <= NrComp; ++i ){
        sort( Comp[i].begin(), Comp[i].end() );
        Comp[i].erase( unique( Comp[i].begin(), Comp[i].end() ), Comp[i].end() );

        for( it = Comp[i].begin(); it != Comp[i].end(); ++it )
            fout << *it << " ";
        fout << "\n";
    }

    return 0;
}