Cod sursa(job #2771755)

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

using uint = unsigned int;

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::vector<uint>> listaAdiacenta(N + 1,
                                                  std::vector<uint>(N + 1, 0));
    std::vector<uint> gradeInterioare(N + 1, 0);

    for (size_t arc = 1; arc <= M; arc++) {
      uint x, y;
      inFile >> x >> y;
      listaAdiacenta[x].push_back(y);
      gradeInterioare[y]++;
    }

    std::queue<uint> q;
    std::vector<uint> topo;

    for (uint i = 1; i <= N; i++) {
      if (gradeInterioare[i] == 0) {
        q.push(i);
        topo.push_back(i);
      }
    }

    while (!q.empty()) {
      uint nod = q.front();
      q.pop();

      for (auto vecin : listaAdiacenta[nod]) {
        gradeInterioare[vecin]--;

        if (gradeInterioare[vecin] == 0) {
          q.push(vecin);
          topo.push_back(vecin);
        }
      }
    }
    std::ofstream outFile;
    outFile.open("sortaret.out", std::ios::out);
    if (outFile.is_open()) {

      for (auto nod : topo)
        outFile << nod << " ";
      outFile << "\n";
      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;
}