Cod sursa(job #2771756)

Utilizator ansalecAlecu Stefan-Iulian ansalec Data 29 august 2021 00:03:55
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <queue>
#include <utility>
#include <array>

using uint = unsigned int;
constexpr auto NMAX = 50002;
int main() {
  std::ifstream inFile;
  inFile.open("sortaret.in", std::ios::in);

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

    std::array<std::vector<uint>, NMAX> listaAdiacenta;
    
    for (int i = 0; i < listaAdiacenta.size(); i++) {
      listaAdiacenta[i].resize(NMAX);
      for (int j = 0; j < listaAdiacenta[i].size(); i++)
        listaAdiacenta[i][j] = 0;
    }
  
    std::array<uint, NMAX> gradeInterioare;
    std::fill(gradeInterioare.begin(), gradeInterioare.end(), 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;
}