Cod sursa(job #1916460)

Utilizator felipeGFilipGherman felipeG Data 9 martie 2017 09:32:55
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#define Nmax 100001
#define Mmax 200001
using namespace std;

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

int n, m, nr;
int fv[ Nmax ], fv1[ Nmax ], st[ Nmax ];
vector < int > graph[ Nmax ], grapht[ Nmax ], solution[ Nmax ];

void read()
{
    int x, y;

    f >> n >> m;

    for ( int i = 1; i <= m; ++ i )
    {
        f >> x >> y;

        graph[ x ].push_back( y );
        grapht[ y ].push_back( x );
    }

}

void DF( int nod )
{
    fv[ nod ] = 1;

    for ( int i = 0; i < (int)graph[ nod ].size(); ++ i )
        if ( not fv[ graph[ nod ][ i ] ] )
           DF( graph[ nod ][ i ] );

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

void DF2( int nod )
{
    fv1[ nod ] = 1;
    solution[ nr ].push_back( nod );

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

int main()
{
    read();

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

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

    g << nr << endl;
    for ( int i = 1; i <= nr; ++ i )
    {
        for ( int j = 0; j < (int)solution[ i ].size(); ++ j )
        {
            g << solution[ i ][ j ] << " ";
        }
        g << endl;
    }

    return 0;
}