Cod sursa(job #1686252)

Utilizator BrandonChris Luntraru Brandon Data 12 aprilie 2016 10:03:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int MaxN = 50005;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

vector <int> G[MaxN], toposort;
queue <int> q;

int EnDeg[MaxN];
bool used[MaxN];
int n, m;

void Dfs(int node) {
  used[node] = true;

  for(auto nxt: G[node]) {
    if(used[nxt]) {
      continue;
    }

    Dfs(nxt);
    toposort.push_back(nxt);
  }
}

void Bfs() {
  while(!q.empty()) {
    int frn = q.front();
    q.pop();

    for(auto nxt: G[frn]) {
      --EnDeg[nxt];

      if(!EnDeg[nxt]) {
        q.push(nxt);
        toposort.push_back(nxt);
      }
    }
  }
}

int main() {
  cin >> n >> m;

  for(int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    ++EnDeg[b];
  }

  /*for(int i = 1; i <= n; ++i) {
    if(!EnDeg[i] and !used[i]) {
      Dfs(i);
      toposort.push_back(i);
    }
  }

  reverse(toposort.begin(), toposort.end());*/

  for(int i = 1; i <= n; ++i) {
    if(!EnDeg[i]) {
      toposort.push_back(i);
      q.push(i);
    }
  }

  Bfs();

  for(auto it: toposort) {
    cout << it << ' ';
  }

  return 0;
}