Cod sursa(job #1526585)

Utilizator DysKodeTurturica Razvan DysKode Data 16 noiembrie 2015 21:35:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

#define N 100010
#define gri 2
#define negru 1
#define alb 0

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector < int > G[ N ], GT[ N ], CTC[ N ];
int U[ N ], i, j, n, m, x, y, mult, st[ N ], sol;

void DFS( int nod , const vector< int > G[] , int t )
{
    int i;
    U[ nod ] = 1;

    for( i = 0 ; i < G[ nod].size() ; i++ )
    {
        if( U[ G[ nod ][ i ] ] == 0 )
        {
            DFS( G[ nod ][ i ] , G , t );
        }
    }

    if( t == 0 )
        st[ ++st[ 0 ] ] = nod;
    else
        CTC[ sol ].push_back( nod );
}

int main()
{
    fin>>n>>m;

    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
        GT[ y ].push_back( x );
    }

    for( i = 1 ; i <= n ; i++ )
    {
        if( U[ i ] == 0 )
        {
            DFS( i , G , 0 );
        }
    }

    memset( U , 0 , sizeof( U ) );

    for( i = n ; i > 0 ; i-- )
    {
        if( U[ st[ i ] ] == 0 )
        {
            ++sol;
            DFS( st[ i ] , GT , 1 );
        }
    }

    fout<<sol<<'\n';

    for( i = 1 ; i <= sol ; i++ )
    {
        for( j = 0 ; j < CTC[ i ].size() ; j++ )
        {
            fout<<CTC[ i ][ j ]<<' ';
        }
        fout<<'\n';
    }

    return 0;
}