Cod sursa(job #2658944)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 15 octombrie 2020 16:06:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
 
int main(int argc, char const *argv[]) {
  
  int n, m;
  cin >> n >> m;
 
  vector < int > rank(n + 1);
  vector < int > poz(n + 1);
  vector < vector < int > > gr(n + 1);
 
  for (int i = 1; i <= m; i ++) {
    int x, y;
    cin >> x >> y;
    gr[x].push_back(y);
    rank[y] ++;
  }
 
  int index = 0;
  queue < int > q;
  for (int i = 1; i <= n; i ++) {
    if (not rank[i]) {
      q.push(i);
    }
  }
 
  while (not q.empty()) {
    int cur = q.front();
    poz[++ index] = cur;
    q.pop();
 
    for (auto x : gr[cur]) {
      if (not rank[x]) {
        continue;
      }
 
      rank[x] --;
      if (not rank[x]) {
        q.push(x);
      }
    }
  }
 
  for (int i = 1; i <= n; i ++) {
    cout << poz[i] << ' ';
  }
  cout << '\n';
}