Cod sursa(job #1921030)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2017 11:08:39
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <list>

using namespace std;

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

list< int > G[ 100010 ] , CTC[ 100010 ];
int idx[100010],mini[100010],i,j,n,m,x,y,st[100010],ans,use[100010];

void tarjan( int nod )
{
    int poz;
    st[ ++st[ 0 ] ] = nod;
    poz = st[ 0 ];
    use[ nod ] = 1;
    idx[ nod ] = ++idx[ 0 ];
    mini[ nod ] = idx[ nod ];
    for( auto it : G[ nod ] )
    {
        if( !use[ it ] )
            tarjan( it );
        mini[ nod ] = min( mini[ nod ] , mini[ it ] );
    }

    if( mini[ nod ] == idx[ nod ] )
    {
        ++ans;
        for( int i = poz ; i <= st[ 0 ] ; i++ )
            CTC[ ans ].push_back( st[ i ] );
        st[ 0 ] = poz - 1;
    }
}

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

    for( i = 1 ; i <= n ; i++ )
    {
        if( !use[ i ] )
            tarjan( i );
    }

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

return 0;
}