Cod sursa(job #1438431)

Utilizator BLz0rDospra Cristian BLz0r Data 19 mai 2015 22:32:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <utility>
using namespace std;

#define Nmax 100002

FILE *f = fopen ( "biconex.in", "r" );
FILE *g = fopen ( "biconex.out", "w" );

vector < int > G[Nmax], Biconexe[Nmax];
stack < pair < int, int > > stiva;
int idx[Nmax], lowlink[Nmax], index = 1, nrBic;

void AddComp ( int x, int y ){
    int ax, ay;
    nrBic++;

    do{
        ax = stiva.top().first;
        ay = stiva.top().second;
        stiva.pop();
        Biconexe[nrBic].push_back ( ax );
        Biconexe[nrBic].push_back ( ay );
    }while ( ax != x || ay != y );
}

void DFS ( int nod ){

    vector < int > :: iterator it;

    idx[nod] = lowlink[nod] = index++;

    for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
        if ( !idx[*it] ){
            stiva.push ( make_pair ( nod, *it ) );
            DFS ( *it );
            lowlink[nod] = min ( lowlink[nod], lowlink[*it] );

            if ( lowlink[*it] >= idx[nod]  )
                AddComp( nod, *it );
        }
        else
            lowlink[nod] = min ( lowlink[nod], idx[*it] );
    }

}

int main(){

    int N, M, x, y;
    vector < int > :: iterator it;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d", &x, &y );
        G[x].push_back ( y );
        G[y].push_back ( x );
    }

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

    fprintf ( g, "%d\n", nrBic );

    for ( int i = 1; i <= nrBic; ++i ){
        sort ( Biconexe[i].begin(), Biconexe[i].end() );
        Biconexe[i].erase ( unique ( Biconexe[i].begin(), Biconexe[i].end() ) , Biconexe[i].end() );
        for ( it = Biconexe[i].begin(); it < Biconexe[i].end(); ++it )
            fprintf ( g, "%d ", *it );
        fprintf ( g, "\n" );
    }

    return 0;
}