Cod sursa(job #2832923)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 14 ianuarie 2022 14:59:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

#define all(a) a.begin(), a.end()
#define range(a, l, r) a.begin() + l, a.begin() + r
#define aall(a, n) a + 1, a + 1 + n
#define arange(a, l, r) a + l, a + r
	
#define maxself(a, b) a = std::max(a, b);
#define minself(a, b) a = std::min(a, b);

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

const int NMAX = 5e4;

int n, m;
std::vector<int> graph[1 + NMAX];
int degIn[1 + NMAX];

std::queue<int> q;

std::vector<int> ans;

void dagSort() {
  for (int i = 1; i <= n; ++i) {
    if (degIn[i] == 0)
      q.push(i);
  }

  while (!q.empty()) {
    int node = q.front();
    q.pop();

    ans.push_back(node);

    for (int i : graph[node]) {
      --degIn[i];

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

int main() {
  inout("sortaret");

  in >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int a, b;
    in >> a >> b;

    graph[a].push_back(b);
    ++degIn[b];
  }

  dagSort();

  for (int i : ans)
    out << i << ' ';
  out << '\n';

  return 0;
}