Cod sursa(job #1038355)

Utilizator TED_996Budaca Eduard TED_996 Data 21 noiembrie 2013 13:24:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include<cstdio>
#include<vector>

using namespace std;

FILE* fout;

int nrNoduri;
vector<int> listeAdiacenta[100008];
vector<int> listeTranspuse[100008];

int postOrdine[100008];
int indPostOrdine = 0;

bool used[100008];

vector<int> componente[100008];
int nrComponente;

void init();
void citire();
void genPostOrdine();
void genComponente();
void afisare();

int main(){
	citire();

    genPostOrdine();
    genComponente();

	afisare();
	return 0;
}

void citire(){
    FILE* fin = fopen("ctc.in", "r");
    int nrMuchii;
    int nod1, nod2;

    //fin >> nrNoduri >> nrMuchii;
    fscanf(fin, "%d%d", &nrNoduri, &nrMuchii);

    while(nrMuchii){
        //fin >> nod1 >> nod2;
        fscanf(fin, "%d\%d", &nod1, &nod2);
        listeAdiacenta[nod1 - 1].push_back(nod2 - 1);
        listeTranspuse[nod2 - 1].push_back(nod1 - 1);
        nrMuchii--;
    }

    fclose(fin);
}

void dfsPostOrdine(int nod);

void genPostOrdine(){
    int i;
    for (i = 0; i < nrNoduri; i++){
        if (!used[i]){
            dfsPostOrdine(i);
        }
    }
}

void dfsPostOrdine(int nod){
    int i;
    used[nod] = 1;
    for (i = 0; i < listeAdiacenta[nod].size(); i++){
        if (!used[listeAdiacenta[nod][i]]){
            dfsPostOrdine(listeAdiacenta[nod][i]);
        }
    }
    postOrdine[indPostOrdine++] = nod;
}

void dfsTranspus(int nod);

void genComponente(){
    int i;
    for (i = 0; i < nrNoduri; i++){
        used[i] = 0;
    }
    for (i = nrNoduri - 1; i >= 0; i--){
        if (!used[postOrdine[i]]){
            nrComponente++;
            dfsTranspus(postOrdine[i]);
        }
    }
}

void dfsTranspus(int nod){
    componente[nrComponente].push_back(nod);
    used[nod] = 1;
    int i;
    for (i = 0; i < listeTranspuse[nod].size(); i++){
        if (!used[listeTranspuse[nod][i]]){
            dfsTranspus(listeTranspuse[nod][i]);
        }
    }
}


void afisare(){
    int i, j;
    fout = fopen("ctc.out", "w");
    fprintf(fout, "%d\n", nrComponente);
    for (i = 1; i <= nrComponente; i++){
        fprintf(fout, "%d", componente[i][0] + 1);
        for (j = 1; j < componente[i].size(); j++){
            fprintf(fout, " %d", componente[i][j] + 1);
        }
        fprintf(fout, "\n");
    }
    fclose(fout);
}