Cod sursa(job #1607413)

Utilizator DysKodeTurturica Razvan DysKode Data 21 februarie 2016 08:37:46
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

void tarjan( int nod )
{
    if( mmt[ nod ] != 0 )
        return;

    mmt[ nod ] = ++tmp;
    bst[ nod ] = tmp;
    st[ ++st[ 0 ] ] = nod;

    for( auto it : Graf[ nod ] )
    {
        tarjan( it );
        bst[ nod ] = min( bst[ it ] , bst[ nod ] );
    }
    CTC[ ans ].push_back( nod );
    if( bst[ nod ] == mmt[ nod ] )
        ++ans;
}

int main()
{
    fin>>n>>m;
    while( m-- )
    {
        fin>>x>>y;
        Graf[ x ].push_back( y );
    }

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

return 0;
}