Cod sursa(job #2771752)

Utilizator ansalecAlecu Stefan-Iulian ansalec Data 28 august 2021 23:30:02
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

//using int = unsigned int;

class Graf {
public:
  std::vector<std::vector<int>> listaDeAdiacenta;
  std::vector<int> gradeInterioare;

  Graf(std::vector<std::pair<int, int>> const &muchii,
       const int numarMuchii) {
    listaDeAdiacenta.resize(numarMuchii + 1);
    gradeInterioare = std::vector<int>{0};
    gradeInterioare.resize(numarMuchii + 1);
    std::fill(gradeInterioare.begin(), gradeInterioare.end(), 0);

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

  void sortareTopologica(const int numarMuchii,
                         std::vector<int> &listaFinala) {
    std::vector<int> gradeInt = gradeInterioare;
    std::vector<int> S {0};

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

    while (!S.empty()) {      
      int nodCoada = S.back();
      S.pop_back();
      listaFinala.push_back(nodCoada);
      for (auto it = this->listaDeAdiacenta[nodCoada].begin();
           it != this->listaDeAdiacenta[nodCoada].end(); it++) {
        gradeInt[*it] -= 1;
        if (gradeInt[*it] != 0)
          S.push_back(*it);
      }
      
    }
  }
};

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

  if (inFile.is_open()) {
    int N, M;
    inFile >> N >> M;

    std::vector<std::pair<int, int>> muchii;
    for (size_t arc = 0; arc < M; arc++) {
      int x, y;
      inFile >> x >> y;
      muchii.push_back(std::make_pair(x - 1, y - 1));
    }

    Graf graf(muchii, N);
    std::vector<int> listaFinala;

    std::ofstream outFile;
    outFile.open("sortaret.out", std::ios::out);
    if (outFile.is_open()) {
      graf.sortareTopologica(N, listaFinala);
      std::reverse(listaFinala.begin(), listaFinala.end());
      for (auto nod : listaFinala)
        outFile << nod + 1 << " ";
      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;
}