Cod sursa(job #2331448)

Utilizator oanaroscaOana Rosca oanarosca Data 29 ianuarie 2019 16:51:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> ns[50005];
queue<int> q;
int extg[50005], solution[50005], solutionNodes;

void topSort() {
  while (!q.empty()) {
    int currentNode = q.front(); q.pop();
//    cout << currentNode << ' ';
    solution[solutionNodes++] = currentNode;
    vector<int>::iterator i;
    for (i = ns[currentNode].begin(); i < ns[currentNode].end(); i++) {
      extg[*i]--;
      if (!extg[*i])
        q.push(*i);
    }
  }
}

int main () {
  int nodes, edges, end1, end2;

  ifstream fi("sortaret.in");
  ofstream fo("sortaret.out");

  fi >> nodes >> edges;
  for (int edge = 1; edge <= edges; edge++)
    fi >> end1 >> end2, ns[end1].push_back(end2), extg[end2]++;

  for (int node = 1; node <= nodes; node++)
    if (!extg[node])
      q.push(node);

  topSort();

  for (int index = 0; index < nodes; index++)
    fo << solution[index] << ' ';

  return 0;
}