Cod sursa(job #3261626)

Utilizator error500Ursaru Tudor Alexandru error500 Data 7 decembrie 2024 09:18:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int NMAX = 50000 + 1;

vector<int> ad[NMAX];
int grad_in[NMAX];
queue<int> q;
int n;

int m;

vector<int> rez;

int main() {
  ifstream in("sortaret.in");
  ofstream out("sortaret.out");
  in >> n >> m;
  while(m--) {
    int a, b;
    in >> a >> b;
    ad[a].push_back(b);
    grad_in[b]++;
  }

  /// Caut nodurile initiale cu grad in. 0
  for(int i = 1; i <= n; i++) {
    if(grad_in[i] == 0) {
      q.push(i);
    }
  }

  while(!q.empty()) {
    const int x = q.front();
    q.pop();
    rez.push_back(x);
    for(const int y : ad[x]) {
      grad_in[y]--;
      if(grad_in[y] == 0) {
        q.push(y);
      }
    }
  }

  for(const int x : rez)
    out << x << ' ';

  return 0;
}