Cod sursa(job #2771732)

Utilizator ansalecAlecu Stefan-Iulian ansalec Data 28 august 2021 21:53:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>

using uint = unsigned int;
typedef struct {
  uint nodSursa, nodDestinatie;
} muchie;

class graf {
public:
  std::vector<std::vector<uint>> listaDeAdiacenta;
  std::vector<uint> gradeInterioare;

  graf(const std::vector<muchie> &muchii, const uint numarMuchii) {
    listaDeAdiacenta.resize(numarMuchii + 1);
    gradeInterioare = std::vector<uint>(numarMuchii + 1, 0);

    for (auto &muchie : muchii) {
      listaDeAdiacenta[muchie.nodSursa].push_back(muchie.nodDestinatie);
      gradeInterioare[muchie.nodDestinatie]++;
    }
  }

  void sortareTopologica(const uint numarMuchii,
                         std::vector<uint> &listaFinala) {
    std::vector<uint> gradeInt = this->gradeInterioare;
    std::vector<uint> S;

    for (uint muchie = 0; muchie <= numarMuchii; muchie++) {
      if (gradeInt[muchie] != 0)
        S.push_back(muchie);
    }

    while (!S.empty()) {
      uint nodCoada = S.back();
      S.pop_back();
      listaFinala.push_back(nodCoada);

      for (uint m : this->listaDeAdiacenta[nodCoada]) {
        gradeInt[nodCoada]--;
        if (gradeInt[nodCoada] == 0)
          gradeInt.push_back(m);
      }
    }
  }
};

int main() {
  std::ifstream inFile;
  inFile.open("sortaret.in", std::ios::in);

  if (inFile.is_open()) {
    uint numarNoduri, numarArce;
    inFile >> numarNoduri >> numarArce;

    std::vector<muchie> muchii;
    for (size_t arc = 0; arc < numarArce; arc++) {
      muchie m;
      inFile >> m.nodSursa >> m.nodDestinatie;
      muchii.push_back(m);
    }
    graf graf(muchii, numarArce + 1);
    std::vector<uint> listaFinala;

    std::ofstream outFile;
    outFile.open("sortaret.out", std::ios::out);
    if (outFile.is_open()) {
      graf.sortareTopologica(numarArce, listaFinala);
      std::reverse(listaFinala.begin(), listaFinala.end());
      for (auto nod : listaFinala)
        outFile << nod << " ";
      outFile.close();
    } else {
      std::cout << "Nu s-a putut scrie in fisier!" << std::endl;
    }
  } else {
    std::cout << "Nu am putut deschide fisierul!" << std::endl;
  }
  inFile.close();
  return 0;
}