Cod sursa(job #2669948)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 8 noiembrie 2020 15:17:42
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int NMAX = 5e4;

int n, m;

std::vector<int> graf[1 + NMAX];
std::queue<int> q;

int degIn[1 + NMAX];

void read() {
  std::ifstream in("sortaret.in");

  in >> n >> m;

  int x, y;
  for (int i = 1; i <= m; ++i) {
    in >> x >> y;

    ++degIn[y];
    graf[x].push_back(y);
  }

  in.close();
}

void sortaret() {
  std::ofstream out("sortaret.out");
  int start = -1;

  for (int i = 1; i <= n; ++i) {
    if (degIn[i] == 0) {
      start = i;
      break;
    }
  }

  q.push(start);

  while (!q.empty()) {
    int nod = q.front();
    q.pop();
    out << nod << ' ';

    for (int vecin: graf[nod]) {
      degIn[vecin]--;

      if (degIn[vecin] == 0)
        q.push(vecin);
    }
  }

  out.close();
}

int main() {
  read();

  sortaret();

  return 0;
}