Cod sursa(job #1891754)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 24 februarie 2017 11:59:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
///FLAVIUS, UBESTE-MA
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

vector <int> G[ 100010 ],GT[ 100010 ],ans[ 100010 ];
int cc,n,m,i,x,y,use[100010],stk[100010];

void DFS1( int nod )
{
    use[ nod ] = 1;
    stk[ ++stk[ 0 ] ] = nod;
    for( auto it : G[ nod ] )
        if( !use[ it ] )
            DFS1( it );
}

void DFS2( int nod )
{
    use[ nod ] = 1;
    ans[ cc ].push_back( nod );
    for( auto it : GT[ nod ] )
        if( !use[ it ] )
            DFS2( it );
}

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 ] )
            DFS1( i );

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

    for( i = n ; i >= 1 ; i-- )
        if( !use[ stk[ i ] ] )
        {
            ++cc;
            DFS2( stk[ i ] );
        }
    fout<<cc<<'\n';
    for( i = 1 ; i <= cc ; i++ )
    {
        for( auto it : ans[ i ] )
            fout<<it<<' ';
        fout<<'\n';
    }

    return 0;
}