Cod sursa(job #2771839)

Utilizator ansalecAlecu Stefan-Iulian ansalec Data 29 august 2021 15:05:50
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using uint = unsigned int;

uint viziteaza(const std::vector<std::vector<bool>> &matriceAdiacenta,
               std::vector<bool> &vizitat, std::vector<uint> &ordine,
               uint index, uint nod) {
  if (vizitat[nod] == true)
    return index;
  vizitat[nod] = true;

  for (size_t vecin = 0; vecin < matriceAdiacenta.size(); vecin++) {
    if (matriceAdiacenta[nod][vecin] != false && !vizitat[vecin])
      index = viziteaza(matriceAdiacenta, vizitat, ordine, index, vecin);
  }

  ordine[index--] = nod;

  return index;
}

std::vector<uint>
sortareTopologica(const std::vector<std::vector<bool>> &matriceAdiacenta) {
  uint numarNoduri = matriceAdiacenta.size();
  std::vector<bool> vizitat(numarNoduri, false);
  std::vector<uint> ordine(numarNoduri, 0);
  uint index = numarNoduri - 1;

  for (size_t nod = 0; nod < numarNoduri; nod++) {
    if (!vizitat[nod])
      index = viziteaza(matriceAdiacenta, vizitat, ordine, index, nod);
  }
  return ordine;
}

int main() {
  std::ifstream inFile;
  inFile.open("sortaret.in", std::ios::in);
  if (inFile.is_open()) {
    int numarNoduri, numarMuchii;
    inFile >> numarNoduri >> numarMuchii;

    std::vector<std::vector<bool>> matriceAdiacenta;
    matriceAdiacenta.resize(numarNoduri);
    std::fill(matriceAdiacenta.begin(), matriceAdiacenta.end(),
              std::vector<bool>(numarNoduri, false));
    for (uint muchie = 0; muchie < numarMuchii; muchie++) {
      uint x, y;
      inFile >> x >> y;
      matriceAdiacenta[x - 1][y - 1] = true;
    }
    std::ofstream outFile;
    outFile.open("sortaret.out", std::ios::out);
    if (outFile.is_open()) {
      std::vector<uint> ordine = sortareTopologica(matriceAdiacenta);
      std::transform(ordine.begin(), ordine.end(), ordine.begin(), [&](auto& x){ return x + 1; });
      for (auto elem : ordine)
        outFile << elem << " ";
      outFile << "\n";
    } else {
      std::cerr << "Nu s-a putut scrie in fisier!" << std::endl;
    }
  } else {
    std::cerr << "Nu am putut deschide fisierul!" << std::endl;
  }
  inFile.close();
  return 0;
}