Cod sursa(job #1089643)

Utilizator cruelifanLouis Cypher cruelifan Data 21 ianuarie 2014 20:25:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int grin[50005];
vector<int> graph[50005];

vector<int> tap(int x){
  vector<int> r_val;
  for(int i = 0; i < graph[x].size(); ++i){
    --grin[graph[x][i]];
    if(!grin[graph[x][i]])
      r_val.push_back(graph[x][i]);
  }
  return r_val;
}

int main(){
  ifstream in("sortaret.in");
  ofstream out("sortaret.out");

  int n, m;
  in >> n >> m;
  for(int i = 1; i <= m; ++i){
    int x, y;
    in >> x >> y;
    graph[x].push_back(y);
    ++grin[y];
  }

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

  vector<int> add, ans;
  while(!q.empty()){
    int now = q.front();
    q.pop();
    ans.push_back(now);

    add = tap(now);
    for(int i = 0; i < add.size(); ++i)
      q.push(add[i]);
  }

  for(int i = 0; i < ans.size(); ++i)
    out << ans[i] << " ";

  return 0;
}