Cod sursa(job #2034071)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 7 octombrie 2017 13:44:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.85 kb
#include <iostream>
#include <fstream>
#define DMAX 100001

using namespace std;

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

typedef struct elem{
    int val;
    elem * urm;
}VECIN;

int n, m;
VECIN * nodSpre[DMAX], *nodIn[DMAX];
bool validare1[DMAX], validare2[DMAX];
int st1[DMAX];
int numar;


void citire(){
    in >> n>> m;
    for(int i = 1; i<= m; i++){
        int x, y;
        in >> x >> y;
        VECIN *deAdaugat = new VECIN;
        deAdaugat -> val = y;
        deAdaugat -> urm  = nodSpre[x];
        nodSpre[x] = deAdaugat;

        VECIN * deAdaugat2 = new VECIN;
        deAdaugat2 -> val = x;
        deAdaugat2 -> urm  = nodIn[y];
        nodIn[y] = deAdaugat2;
    }
}

void parcurgereDF(int el,VECIN *nod[], bool viz[]){//ok
    int st[DMAX], varf;
    bool ok = false;
    st[1] = el;
    viz[el] = true;
    varf = 1;
    while (varf != 0){
        VECIN * parcurg ;
        parcurg = nod[st[varf]];
        ok = false;
        while(parcurg != NULL){
            if(viz[parcurg -> val] == false){
                ok = true;
                st[++ varf] = parcurg -> val;
                viz[parcurg -> val] = true;
                break;
            }else{
                parcurg = parcurg -> urm;
            }
        }
        if(ok == false && varf != 0){
            st1[++st1[0]] = st[varf];
            varf --;
        }
    }
}

void parcurgereDFFinala(int el,VECIN *nod[], bool viz[],int nr){//ok
    int st[DMAX], varf;
    bool ok ;
    st[1] = el;
    viz[el] = true;
    varf = 1;
    while (varf != 0){
        VECIN * parcurg;
        parcurg = nod[st[varf]];
        ok = false;
        while(parcurg != NULL){
            if(viz[parcurg -> val] == false){
                ok = true;
                st[++ varf] = parcurg -> val;
                viz[parcurg -> val] = true;
                break;
            }else{
                parcurg = parcurg -> urm;
            }
        }
        if(ok == false && varf != 0) {
            VECIN *deAdaugat = new VECIN;
            deAdaugat -> val = st[varf];
            deAdaugat -> urm  = nodSpre[nr];
            nodSpre[nr] = deAdaugat;
            varf --;
        }
    }
}

void construireStivaDf(){
    for(int i = 1; i<=n ; i++){
        if(validare1[i] == false){
            parcurgereDF(i, nodSpre, validare1);
        }
    }
}

void parcurgereInversa(){
    while(st1[0] != 0){
        if(validare2[st1[st1[0]]] == false){
            nodSpre[++numar] = NULL;
            parcurgereDFFinala(st1[st1[0]], nodIn, validare2, numar);
        }
        st1[0]--;
    }
}

void afisare(){
    out << numar <<'\n';
    for(int i = 1; i<= numar; i++){
        while (nodSpre[i] != NULL){
            out << nodSpre [i]-> val << ' ';
            nodSpre[i] = nodSpre[i]->urm;
        }
        out << '\n';
    }
}

int main() {
    citire();
    construireStivaDf();
    parcurgereInversa();
    afisare();
    return 0;
}