Cod sursa(job #1520594)

Utilizator jimcarterJim Carter jimcarter Data 9 noiembrie 2015 04:01:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

FILE *f = fopen ( "ctc.in" , "r" ) , *g = fopen ( "ctc.out" , "w" );

const int MAX = 100005;
int N , M , i , j , x , y , nrComp , node;
bool visited [ MAX ];
vector < int > edge [ MAX ] , edgeT [ MAX ] , sccs [ MAX ];
stack < int > finish;

void read()
{
    fscanf ( f , "%d %d" , &N , &M );
    for ( i = 1 ; i <= M ; i ++ )
    {
        fscanf ( f , "%d %d" , &x , &y );
        edge [ x ] . push_back ( y );
        edgeT [ y ] . push_back ( x );
    }
}

void dfs ( int node )
{
    visited [ node ] = true;
    for ( int i = 0 ; i < edge [ node ] . size() ; i ++ )
        if ( !visited [ edge [ node ] [ i ] ] )
            dfs ( edge [ node ] [ i ] );
    finish . push ( node );
}

void dfsT ( int node )
{
    visited [ node ] = false;
    sccs [ nrComp ] . push_back ( node );
    for ( int i = 0 ; i < edgeT [ node ] . size() ; i ++ )
        if ( visited [ edgeT [ node ] [ i ] ] )
            dfsT ( edgeT [ node ] [ i ] );
}

void scc()
{
    for ( i = 1 ; i <= N ; i ++ )
        if ( !visited [ i ] )
            dfs ( i );
    while ( !finish.empty() )
    {
        node = finish . top() , finish . pop();
        if ( visited [ node ] )
        {
            nrComp ++;
            dfsT ( node );
        }
    }
}

void print()
{
    fprintf ( g , "%d\n" , nrComp );
    for ( i = 1 ; i <= nrComp ; i ++ )
    {
        for ( j = 0 ; j < sccs [ i ] . size() ; j ++ )
            fprintf ( g , "%d " , sccs [ i ] [ j ] );
        fprintf ( g , "\n" );
    }
}

int main()
{
    read();
    scc();
    print();
    return 0;
}