Cod sursa(job #441876)

Utilizator alexandru92alexandru alexandru92 Data 13 aprilie 2010 16:56:01
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 13, 2010, 4:08 PM
 */
#include <stack>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define SIZE 8219
#define Nmax 100000

/*
 * 
 */
using namespace std;
ifstream in;
typedef pair< int, int > pr;
char file[SIZE];
int N, ifile, idx, ccount;
int dfn[Nmax], lowlink[Nmax];
stack< pr > S;
vector< vector< int > > G, BCC;
inline void read( int& x )
{
    x=0;
    while( file[ifile] < '0' || file[ifile] > '9' )
        if( ++ifile == SIZE )
        {
            in.read( file, SIZE );
            ifile=0;
        }
    while( file[ifile] >= '0' && file[ifile] <= '9' )
    {
        x=x*10+file[ifile]-'0';
        if( ++ifile == SIZE )
        {
            in.read( file, SIZE );
            ifile=0;
        }
    }
}
inline void GetBiconexC( int x, int f )
{
    pr vertex, current( x, f );
    vector< bool > uz( N );
    BCC.resize(ccount+1);
    do
    {
        vertex=S.top(); S.pop();
        if( !uz[vertex.first] )
        {
            BCC[ccount].push_back(vertex.first+1);
            uz[vertex.first]=true;
        }
        if( !uz[vertex.second] )
        {
            BCC[ccount].push_back(vertex.second+1);
            uz[vertex.second]=true;
        }
    }while( vertex != current );
    ++ccount;
}
inline void DFS( int x )
{
    vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
    dfn[x]=lowlink[x]=(++idx);
    for( ; it < iend; ++it )
    {
         if( !dfn[*it] )
        {
            S.push( pr( *it, x ) );
            DFS( *it );
            lowlink[x]=min( lowlink[x], lowlink[*it] );
            if( lowlink[*it] >= dfn[x] )
                GetBiconexC( *it, x );
        }
        else lowlink[x]=min( lowlink[x], dfn[*it] );
    }
}
int main(int argc, char** argv)
{
    int M, x, y;
    in.open( "biconex.in" );
    read(N); read(M);
    G.resize(N);
    for( ; M; --M )
    {
        read(x); read(y);
        --x, --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for( x=0; x < N; ++x )
        if( !dfn[x] )
            DFS( x );
    ofstream out( "biconex.out" );
    out<<ccount<<'\n';
    for( x=0; x < ccount; ++x )
    {
        copy( BCC[x].begin(), BCC[x].end(), ostream_iterator<int>( out, " " ) );
        out<<'\n';
    }
    return EXIT_SUCCESS;
}