Cod sursa(job #2436475)

Utilizator minculescualex9Minculescu Alex minculescualex9 Data 5 iulie 2019 22:03:48
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");

#define MAX 100000

int a[MAX][MAX], nrNod, nrMuchii;
int ordine[MAX], index_ordine, grad_in[MAX];
bool viz[MAX];

void citire(){
    //Memoram graful orientat intr-o matrice de adiacenta;
    //Coloana 0 va pastra gradul interior al nodului i;
    fin >> nrNod >> nrMuchii;
    for(int i = 1; i <= nrMuchii; i++){
        int x, y;
        fin >> x >> y;
        a[x][0]++;
        a[x][a[x][0]] = y;
        grad_in[y]++;
    }
}

void afisare_lista(){
    fout << "Lista de adiacenta este: \n";
    for(int i = 1; i <= nrNod; i++){
        int grad = a[i][0];
        fout << i << ": ";
        for(int j = 1; j <= grad; j++)
            fout << a[i][j] << " ";
        fout << "\n";
    }

    fout << "Gradul interior al nodurile este: \n";
    for(int i = 1; i <= nrNod; i++)
        fout << grad_in[i] << " ";
    fout << "\n";
}

void makeset(){
    for(int i = 1; i <= nrNod; i++)
        viz[i] = 0;
}

void dfs(int nod){
    viz[nod] = 1;

    int grad = a[nod][0];
    for(int j = 1; j <= grad; j++)
        if(!viz[a[nod][j]])
            dfs(a[nod][j]);

    ordine[index_ordine--] = nod;
}

void afisare_topsort(){
//    fout << "Ordinea topologica gasita este: ";
    for(int i = 1; i <= nrNod; i++)
        fout << ordine[i] << " ";
//    fout << "\n";
}

void TopSort(){
    makeset();  //initializam vec. viz[]
    index_ordine = nrNod; //pozitia unde trebuie introdus nodul

    for(int i = 1; i <= nrNod; i++)
        if(!viz[i] && grad_in[i] == 0) //daca nu e vizitat
            dfs(i);

    afisare_topsort();
}

int main()
{
    citire();
//    afisare_lista();
    TopSort();
    return 0;
}