Cod sursa(job #1757828)

Utilizator din99danyMatei Daniel din99dany Data 15 septembrie 2016 22:06:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX 100005

vector < int > v[ NMAX ];
stack < pair < int , int > > Q;
vector < int > aux;
vector < vector < int> > sol;

int  upBound[ NMAX ],
    lowBound[ NMAX ];

void biconex( int nod, int tata, int niv ){

    int x, y;

    upBound[ nod ] = lowBound[ nod ] = niv;
    vector < int > :: iterator it;

    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it ){
        if( *it == tata ) continue;
        if( !lowBound[ *it ] ){
            Q.push( { nod, *it } );
            biconex( *it, nod, niv + 1 );
            lowBound[ nod ] = min( lowBound[ nod ], lowBound[ *it ] );
            if( upBound[ nod ] <= lowBound[ *it ] ){
                aux.clear();
                do{
                    x = Q.top().first;
                    y = Q.top().second;
                    Q.pop();
                    aux.push_back( x ); aux.push_back( y );
                }while( x != nod || y != *it );
                sol.push_back( aux );
            }
        }
        else
            lowBound[ nod ] = min( lowBound[ nod ], lowBound[ *it ] );
    }

}

int main()
{

    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    int n, m, i, j, x, y;

    scanf("%d%d",&n,&m);
    while( m-- ){
        scanf("%d%d",&x,&y);
        v[ x ].push_back( y );
        v[ y ].push_back( x );
    }


    biconex( 1, 0, 1 );

    printf("%d\n",sol.size());
    for( i = 0; i < sol.size(); ++i ){
        sort( sol[ i ].begin(), sol[ i ].end() );
        for( j = 0; j < sol[ i ].size(); ++j )
            if( j == 0 || sol[ i ][ j ] != sol[ i ][ j - 1 ] ) printf("%d ",sol[ i ][ j ]);
        printf("\n");
    }

    return 0;

}