Cod sursa(job #1650721)

Utilizator DysKodeTurturica Razvan DysKode Data 11 martie 2016 20:04:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> G[100010],GT[100010],CTC[100010];
int a,b,c,d,use[100010],i,j,n,m,x,y,st[100010],ans;

void DF( vector <int> G[], int nod, int t )
{
    use[ nod ] = 1;
    for( vector<int>::iterator it = G[ nod ].begin() ; it != G[ nod ].end() ; it++ )
        if( !use[ *it ] )
            DF( G , *it , t );

    if( t == 0 )
        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( G , i , 0 );
    for( i = 1 ; i <= n ; i++ )
        use[ i ] = 0;
    for( i = n ; i >= 1 ; i-- )
        if( !use[ st[ i ] ] )
        {
            ++ans;
            DF( GT , st[ i ] , 1 );
        }

    fout<<ans<<'\n';
    for( i = 1 ; i <= ans ; i++ )
    {
        for( vector<int>::iterator it = CTC[ i ].begin() ; it != CTC[ i ].end() ; it++ )
            fout<<*it<<' ';
        fout<<'\n';
    }


return 0;
}