Cod sursa(job #1650535)

Utilizator felipeGFilipGherman felipeG Data 11 martie 2016 18:57:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <queue>
#include <vector>
#define Nmax 100010
using namespace std;

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

int n, m, viz[ Nmax ], st[ Nmax ], comp[ Nmax ], nr, x, y;
vector < int > v[ Nmax ], t[ Nmax ], s[ Nmax ];

void DF( int nod )
{
    viz[ nod ] = 1;
    for ( int i = 0; i < (int)v[ nod ].size(); ++ i )
        if ( not viz[ v[ nod ][ i ] ] )
            DF( v[ nod ][ i ] );

    st[ ++ st[ 0 ] ] = nod;
}

void DF2 ( int nod )
{
    comp[ nod ] = 1;
    s[ nr ].push_back( nod );

    for ( int i = 0; i < (int)t[ nod ].size(); ++ i )
        if ( not comp[ t[ nod ][ i ] ] )
            DF2( t[ nod ][ i ] );
}

int main()
{
    fscanf( f, "%d%d", &n, &m );

    for ( int i = 1; i <= m; ++ i )
    {
        fscanf( f, "%d%d", &x, &y );
        v[ x ].push_back( y );
        t[ y ].push_back( x );
    }

    for ( int i = 1; i <= n; ++ i )
        if ( not viz[ i ] )
            DF( i );

    while ( st[ 0 ] )
    {
        if ( not comp[ st[ st[ 0 ] ] ] )
        {
            nr ++;
            DF2( st[ st[ 0 ] -- ] );
        }
        else st[ 0 ]--;
    }

    fprintf( g, "%d\n", nr );
    for ( int i = 1; i <= nr; ++ i )
    {
        for ( int j = 0; j < (int)s[ i ].size(); ++ j )
             fprintf( g, "%d ", s[ i ][ j ] );
        fprintf( g, "\n" );
    }
    return 0;
}