Cod sursa(job #1317808)

Utilizator mvcl3Marian Iacob mvcl3 Data 15 ianuarie 2015 10:52:48
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

#define Max_Size 100002

using namespace std;

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


int N, M, Count;

bool Viz[Max_Size];

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

stack < int > my_Stack;

inline void Read_Data()
{
    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);
    }
}

void DFS1(int nod)
{
    Viz[nod] = 1, my_Stack.push(nod);

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

void DFS2(int nod)
{
    Viz[nod] = 1, Sol[Count].push_back( nod );

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

int main()
{
    Read_Data();

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

    memset(Viz, 0, sizeof( Viz ));

    for(; !my_Stack.empty(); my_Stack.pop())
        if(!Viz[ my_Stack.top() ]) ++Count, DFS2( my_Stack.top());

    ofstream out( oname );

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

        out << '\n';
    }
}