Cod sursa(job #460688)

Utilizator BitOneSAlexandru BitOne Data 3 iunie 2010 16:57:05
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <stack>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define Nmax 100111

/*
 *
 */
using namespace std;
typedef pair< int, int > pr;
int N, indx, nrc;
int idx[Nmax], lowlink[Nmax];
stack< pr > S;
vector< int > G[Nmax], BCC[Nmax];
inline void GetBCC( pr p0 )
{
    bool was[Nmax]={0};
    pr p;
    ++nrc;
    do
    {
        p=S.top(); S.pop();
        if( !was[p.first] )
        BCC[nrc].push_back(p.first);
        if( !was[p.second] )
        BCC[nrc].push_back(p.second);
        was[p.first]=was[p.second]=true;
    }while( p != p0 );
}
inline void DFS( int x )
{
    idx[x]=lowlink[x]=++indx;
    if( G[x].empty() )
        return;
    vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
    for( ; it < iend; ++it )
        if( 0 == idx[*it] )
        {
            S.push( pr( x, *it ) );
            DFS( *it );
            lowlink[x]=min( lowlink[x] , lowlink[*it] );
            if( lowlink[*it] >= idx[x] )
                GetBCC( pr( x, *it ) );
        }
        else lowlink[x]=min( lowlink[x] , idx[*it] );
}
int main( void )
{
    int M, x, y;
    ifstream in( "biconex.in" );
    for( in>>N>>M; M; --M )
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for( x=1; x <= N; ++x )
        if( 0 == idx[x] )
            DFS(x);
    ofstream out( "biconex.out" );
    out<<nrc<<'\n';
    for( x=1; x <= nrc; ++x )
    {
        copy( BCC[x].begin(), BCC[x].end(), ostream_iterator< int >( out, " " ) );
        out<<'\n';
    }
    return EXIT_SUCCESS;
}