Cod sursa(job #1548047)

Utilizator DysKodeTurturica Razvan DysKode Data 10 decembrie 2015 12:48:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
using namespace std;

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

#define N 100010

vector <int>G[N],GT[N],CTC[N];
int use[N],st[N],i,j,k,l,o,sol,n,m,x,y;

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

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

    if( t == 1 )
        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( use[ i ] == 0 )
        {
            DFS( i , G , 1 );
        }
    }

    for( i = 1 ; i <= n ; i++ )
        use[ i ] = 0;

    for( i = n ; i >= 1 ; i-- )
    {
        if( use[ st[ i ] ] == 0 )
            ++sol,DFS( st[ i ] , GT , 0 );
    }
    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;
}