Cod sursa(job #3300712)

Utilizator vlvdVlad Hosu vlvd Data 18 iunie 2025 17:27:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m;
vector<vector<int>> nodes;
vector<int> in_grades, res;

int main() {
  fin >> n >> m;
  in_grades.resize(n + 1, 0);
  nodes.resize(n + 1);

  int x, y;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y;
    nodes[x].push_back(y);
    in_grades[y]++;
  }

  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (in_grades[i] == 0)
      q.push(i);
  }

  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    res.push_back(curr);

    for (auto &child : nodes[curr]) {
      in_grades[child]--;
      if (in_grades[child] == 0) {
        q.push(child);
      }
    }
  }

  for (auto &nod : res) {
    fout << nod << " ";
  }
  fout << '\n';
}