Cod sursa(job #1241359)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 13 octombrie 2014 13:32:41
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

#define  size  100001

int n, m, sw[size], solind;
vector<int> graf[size], tgraf[size], sol[size], stack;

void df1(int nod){
    stack.push_back(nod);
    sw[nod] = 1;
    for (vector<int> :: iterator it = graf[nod].begin(); it < graf[nod].end(); it++) {
        if (sw[*it] == 0) {
            df1(*it);
        }
    }
}

void df2(int nod) {
    sol[solind].push_back(nod);
    sw[nod] = 1;
    for( vector<int> :: iterator it = tgraf[nod].begin(); it < tgraf[nod].end(); it ++) {
        if ( sw[*it] == 0) {
            df2(*it);
        }
    }
}

void solve() {
    for (int i = 1; i <=n ; i++) {
        if ( sw[i] == 0){
            df1(i);
        }
    }
    memset(sw, 0, sizeof(sw));
    solind = 0;
    for (int i = 0; i<n; i++) {
        int nod = stack[i];
        if (sw[nod] == 0) {
            df2(nod);
            solind ++;
        }
    }
}

void afisare() {
    ofstream g("ctc.out");
    g << solind << '\n';
    for (int i = 0 ; i < solind ; i ++) {
        for (vector<int> :: iterator it  = sol[i].begin(); it < sol[i].end(); it ++) {
            g << *it <<' ' ;
        }
        g << '\n';
    }
    g.close();
}

void citire() {
    ifstream f("ctc.in");
    f >> n >> m;
    for (int i = 1; i <=m; i++) {
        int x, y;
        f >> x >> y ;
        graf[x].push_back(y);
        tgraf[y].push_back(x);
    }
    f.close();
}

int main()
{
    citire();
    solve();
    afisare();
    return 0;
}