Cod sursa(job #2787569)

Utilizator andrei.gatejAndrei Gatej andrei.gatej Data 23 octombrie 2021 18:18:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <list>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

// Link pt `GraphSolver`: https://github.com/Andrei0872/Algorithms/blob/master/GraphSolver/main.cpp

using namespace std;


int main () {
  ifstream in("sortaret.in");
  int N, M;

  in >> N >> M;
  list<int> *adjList = new list<int>[N + 1];
  int* innerDegMap = new int[N + 1];

  // Nodes with inner degree 0.
  queue<int> independentNodes;

  int x, y;
  for (int i = 0; i < M; i++) {
    in >> x >> y;

    adjList[x].push_back(y);
    // innerDegMap[y] -= ~innerDegMap[y];
    innerDegMap[y]++;
  }

  // for (int i = 1; i <= N; i++) {
  //   cout << innerDegMap[i] << ' ';
  // }

  in.close();

  for (int i = 1; i <= N; i++) {
    if (innerDegMap[i] == 0) {
      independentNodes.push(i);
    }
  }

  ofstream out("sortaret.out");
  while (!independentNodes.empty()) {
    int crtNode = independentNodes.front();
    independentNodes.pop();

    out << crtNode << ' ';

    for (int childNode : adjList[crtNode]) {
      if (--innerDegMap[childNode] == 0) {
        independentNodes.push(childNode);
      }
    }
  }

  out.close();

  delete []adjList;
  delete innerDegMap;

  return 0;
}