Cod sursa(job #1916631)

Utilizator felipeGFilipGherman felipeG Data 9 martie 2017 09:59:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <queue>
#include <vector>
#define Nmax 100010
using namespace std;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

int n, m, viz[ Nmax ], st[ Nmax ], comp[ Nmax ], nr, x, y;
vector < int > v[ Nmax ], t[ Nmax ], s[ Nmax ];

void DF( int nod )
{
    viz[ nod ] = 1;
    for ( int i = 0; i < (int)v[ nod ].size(); ++ i )
        if ( not viz[ v[ nod ][ i ] ] )
            DF( v[ nod ][ i ] );

    st[ ++ st[ 0 ] ] = nod;
}

void DF2 ( int nod )
{
    comp[ nod ] = 1;
    s[ nr ].push_back( nod );

    for ( int i = 0; i < (int)t[ nod ].size(); ++ i )
        if ( not comp[ t[ nod ][ i ] ] )
            DF2( t[ nod ][ i ] );
}

int main()
{
    f >> n >> m;

    for ( int i = 1; i <= m; ++ i )
    {
        f >> x >> y;
        v[ x ].push_back( y );
        t[ y ].push_back( x );
    }

    for ( int i = 1; i <= n; ++ i )
        if ( not viz[ i ] )
            DF( i );

    while ( st[ 0 ] )
    {
        if ( not comp[ st[ st[ 0 ] ] ] )
        {
            nr ++;
            DF2( st[ st[ 0 ] -- ] );
        }
        else st[ 0 ]--;
    }

    g << nr << '\n';
    for ( int i = 1; i <= nr; ++ i )
    {
        for ( int j = 0; j < (int)s[ i ].size(); ++ j )
             g << s[ i ][ j ] << " ";
        g << '\n';
    }
    return 0;
}