Cod sursa(job #2771494)

Utilizator ansalecAlecu Stefan-Iulian ansalec Data 27 august 2021 16:35:22
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <fstream>
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <utility>

class Graf {
private:
  unsigned int numarNoduri;
  std::list<int> *l;

public:
  Graf(unsigned int _numarNoduri) : numarNoduri(_numarNoduri) {
    l = new std::list<int>[numarNoduri];
  }

  void adaugaNod(unsigned int nodInceput, unsigned int nodSfarsit) {
    l[nodInceput].push_back(nodSfarsit);
  }
  void sortareTopologica() {
    int *gradeInterioare = new int[numarNoduri]{0};

    for (size_t i = 0; i < numarNoduri; i++) {
      for (auto it = l[i].begin(); it != l[i].end(); it++)
        gradeInterioare[*it]++;
    }

    std::queue<unsigned int> coada;
    for (size_t i = 0; i < numarNoduri; i++)
      if (gradeInterioare[i] == 0)
        coada.push(i);

    while (!coada.empty()) {
    }
  }
};
int main() {
  std::ifstream inFile;
  inFile.open("sortaret.in", std::ios::in);

  if (inFile.is_open()) {
    unsigned int numarNoduri, numarLinii;
    inFile >> numarNoduri >> numarLinii;

    std::list<unsigned int> *l = new std::list<unsigned int>[numarNoduri + 1];
    unsigned int nodInceput, nodSfarsit;
    for (size_t linie = 0; linie < numarLinii; linie++) {
      inFile >> nodInceput >> nodSfarsit;
      l[nodInceput].push_back(nodSfarsit);
    }

    unsigned int *gradInterior = new unsigned int[numarNoduri]{0};
    // iterate over all edges
    for (size_t nod = 0; nod < numarNoduri; nod++) {
      for (auto it = l[nod].begin(); it != l[nod].end(); it++) {
        gradInterior[*it]++;
      }
    }
    std::queue<int> coadaNoduri;
    for (size_t nod = 0; nod < numarNoduri; nod++) {
      if (gradInterior[nod] == 0) {
        coadaNoduri.push(nod);
      }
    }

    std::ofstream outFile;
    outFile.open("sortaret.out", std::ios::out);
    if (outFile.is_open()) {
      while (!coadaNoduri.empty()) {
        int f = coadaNoduri.front();
        outFile << ((f != 0) ? (std::to_string(f) + " ") : (""));
        coadaNoduri.pop();
        for (auto it = l[f].begin(); it != l[f].end(); it++) {
          gradInterior[*it]--;
          if (gradInterior[*it] == 0) {
            coadaNoduri.push(*it);
          }
        }
      }
      outFile.close();
    } else
      std::cout << "Nu s-a putut scrie in fisier!" << std::endl;
    inFile.close();
  } else
    std::cout << "Nu am putut deschide fisierul!" << std::endl;
  return 0;
}