Cod sursa(job #2493152)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 16 noiembrie 2019 08:53:41
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int i, j, n, m , k;

vector<int> graph[50001];
vector<int> noIncomingEdges;
int incoming[50001];

int main() {

  ifstream fin("sortaret.in");
  ofstream fout("sortaret.out");

  fin>>n>>m;
  int a, b;

  for(int i = 0; i < m; i++) {
    fin>>a>>b;
    graph[a].push_back(b);
    incoming[b]++;
  }

  for (int i = 1; i <= n; i++)
    if (incoming[i] == 0)
      noIncomingEdges.push_back(i);

  while(!noIncomingEdges.empty()) {
    int currNode = noIncomingEdges.back();
    fout<<currNode<<" ";
    noIncomingEdges.pop_back();
    int size = graph[currNode].size();
    for (int i = 0; i < size; i++) {
      int nextNode = graph[currNode][i];
      incoming[nextNode]--;
      if (incoming[nextNode] == 0)
        noIncomingEdges.push_back(nextNode);
    }
  }

  return 0;
}