Cod sursa(job #2032298)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 4 octombrie 2017 19:58:54
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 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[cur] = ++ index;
    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';
}