Cod sursa(job #1373371)

Utilizator mvcl3Marian Iacob mvcl3 Data 4 martie 2015 18:18:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <stack>

#define Max_Size 100009

using namespace std;

const char iname[] = "ctc.in";
const char oname[] = "ctc.out";

int N, M, ctc;

bool Viz[Max_Size];

vector < int > V[Max_Size], W[Max_Size], Sol[Max_Size];

stack < int > my_Stack;

void DF_Plus( int nod )
{
    Viz[ nod ] = 1;

    for(vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        if(!Viz[ *it ]) DF_Plus( *it );

    my_Stack.push( nod );
}

void DF_Minus( int nod )
{
    Viz[nod] = 1;
    Sol[ctc].push_back( nod );

    for(vector < int > :: iterator it = W[nod].begin(); it != W[nod].end(); ++it)
        if( !Viz[ *it ] )   DF_Minus( *it );
}

int main()
{
    ifstream in( iname );

    in >> N >> M;
    for(int x, y, i = 1; i <= M; ++i)   {
        in >> x >> y;

        V[x].push_back(y);
        W[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i)
        if( !Viz[i])    DF_Plus(i);

    for(int i = 1; i <= N; ++i) Viz[i] = 0;

    while( !my_Stack.empty())   {
        if( !Viz[ my_Stack.top() ]) {
            ++ctc;
            DF_Minus( my_Stack.top() );
        }

        my_Stack.pop();
    }

    ofstream out( oname );

    out << ctc << '\n';
    for(int i = 1; i <= ctc; ++i)   {
        for(int j = 0; j < Sol[i].size(); ++j)    out << Sol[i][j] << ' ';

        out << '\n';
    }

    return 0;
}