Cod sursa(job #1611953)

Utilizator DysKodeTurturica Razvan DysKode Data 24 februarie 2016 16:47:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

vector <int> G[100001],CTC[100001],GT[100001];
int use[100001],bst[100001],st[100001],i,j,n,m,x,y,ans=1,tmp;

void DF( int nod, vector<int> G[], int t )
{
    use[ nod ] = 1;
    for( auto it : G[ nod ] )
        if( !use[ it ] )
            DF( it , G , t );
    if( t )
        st[ ++st[ 0 ] ] = nod;
    else
        CTC[ ans ].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 ] )
            DF( i , G , 1 );

    memset( use , 0 , sizeof( use ) );

    for( i = n ; i >= 1 ; i-- )
        if( !use[ st[ i ] ] )
            ++ans,DF( st[ i ] , GT , 0 );

    fout<<ans-1<<'\n';
    for( i = 2 ; i <= ans ; i++,fout<<'\n' )
        for( auto it : CTC[ i ] )
            fout<<it<<' ';

return 0;
}