Cod sursa(job #719998)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 22 martie 2012 11:31:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<fstream>
#include<cstdio>
#include<vector>
#define INfile "ctc.in"
#define OUTfile "ctc.out"

#define pb push_back
#define NMAX 100001

using namespace std ;

//ifstream F ( INfile ) ;
//ofstream G ( OUTfile ) ;

int N , M , ctc , nre ;
int viz [ NMAX ] , V [ NMAX ] ;
vector < int > V1 [ NMAX ] , V2 [ NMAX ] , SOL [ NMAX ] ;

void read () ;
void solve () ;
void write () ;
void DFS1 ( int k ) ;
void DFS2 ( int k ) ;

int main ()
{
    read () ;
    solve () ;
    write () ;

    //F.close () ;
    //G.close () ;

    return 0 ;
}

void read ()
{
    int i , x , y ;
    freopen ( INfile , "r" , stdin ) ;
    //F >> N >> M ;
    scanf ( "%d%d" , & N , & M ) ;
    for ( i = 1 ; i <= M ; ++ i )
    {
        scanf ( "%d%d" , & x , & y ) ;
        //F >> x >> y ;
        V1 [ x ].pb ( y ) ;
        V2 [ y ].pb ( x ) ;
    }
}

void solve ()
{
    int i ;
    for ( i = 1 ; i <= N ; ++ i )
        if ( ! viz [ i ] )
            DFS1 ( i ) ;

    for ( i = N ; i > 0 ; -- i )
    if ( viz [ V [ i ] ] )
    {
        ++ ctc ;
        DFS2 ( V [ i ] ) ;
    }
}

void DFS1 ( int k )
{
    int i ;
    viz [ k ] = 1 ;

    for ( i = V1 [ k ].size () - 1 ; i > -1 ; --i )
        if ( ! viz [ V1 [ k ][ i ] ] )
            DFS1 ( V1 [ k ][ i ] ) ;
    V [ ++ nre ] = k ;
}

void DFS2 ( int k )
{
    int i ;
    viz [ k ] = 0 ;
    SOL [ ctc ].pb ( k ) ;
    for ( i = V2 [ k ].size () - 1 ; i > -1 ; --i )
        if ( viz [ V2 [ k ][ i ] ] )
            DFS2 ( V2 [ k ][ i ] ) ;
}
void write ()
{
    int i , j ;
    freopen ( OUTfile , "w" , stdout ) ;
    printf ( "%d\n" , ctc ) ;
    for ( i = 1 ; i <= ctc ; ++ i )
    {
        for ( j = SOL [ i ].size () - 1 ; j > -1 ; -- j )
            printf ( "%d " , SOL [ i ][ j ] );
        printf( "\n" ) ;
    }
}