Cod sursa(job #1380202)

Utilizator bodyionitaIonita Bogdan Constantin bodyionita Data 6 martie 2015 23:19:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define NMAX 100001
#define pb push_back

using namespace std;

int N, M, i, j, x, y;
int Low[NMAX];
int Lvl[NMAX];
int T[NMAX];
int Written[NMAX];
vector< int > G[NMAX];
vector< vector < int > > Comp;
stack< pair< int, int > > Muchii;
bool USED[NMAX];

inline void MemComp( int X, int Y )
{
    vector< int > C;
    pair< int, int > Mct, M1 = make_pair( X, Y ), M2 = make_pair( Y, X );
    do
    {
        Mct = Muchii.top();
        C.pb( Mct.first );
        C.pb( Mct.second );
        Muchii.pop();
    }
    while( Mct != M1 && Mct != M2 );
    Comp.pb( C );
}

inline void DF( int NOD )
{
    USED[NOD] = true;
    Low[NOD] = Lvl[NOD];
    for( vector< int >::iterator it = G[NOD].begin(); it != G[NOD].end(); it++ )
    {
        if( *it != T[NOD] && Lvl[NOD] > Lvl[*it] )
            Muchii.push( make_pair( *it, NOD ) );

        if( !USED[*it] )
        {
            Lvl[*it] = Lvl[NOD] + 1;
            T[*it] = NOD;

            DF( *it );

            if( Low[NOD] > Low[*it] )
                Low[NOD] = Low[*it];

            if( Low[*it] >= Lvl[NOD] )
                MemComp( *it, NOD );
        }
        else if( *it != T[NOD] && Low[NOD] > Lvl[*it] )
            Low[NOD] = Lvl[*it];
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d", &N, &M);
    while( M-- )
    {
        scanf("%d%d",&x, &y);
        G[x].pb( y );
        G[y].pb( x );
    }
    memset( USED, false, sizeof(USED) );
    Lvl[1] = 1;
    DF( 1 );
    printf("%d\n", Comp.size());
    for( i=0; i<Comp.size(); i++ )
    {
        for( j=0; j<Comp[i].size(); j++ )
            Written[Comp[i][j]] = 1;
        for( j=0; j<Comp[i].size(); j++ )
            if( Written[Comp[i][j]])
            {
                printf("%d ",Comp[i][j]);
                Written[Comp[i][j]] = 0;
            }
        printf("\n");
    }
    return 0;
}