Topological Sort

Topological Sort is a classical algorithm applied on a Directed Acyclic Graph. In a DAG, you can always put the graph in a topological order. A topological is when you only have arrows pointing from a left node to a right node. Here is a exemple of a topolgical sort :



One possibility of topological ordering is 7 5 1 2 3 4 0 6. So here our goal is to find a technique that can help us to find a topological order. One technique is to do a vector<vector<int>> and to put all the node's fathers in it and then use recursion on all the empty nodes. Here is a C++ code that finds you a topological order. If this order doesn't exist then it will print -1 :

C++ code

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
int N;
vector<unordered_set<int>> dad(1001);
vector<int> ret;
 
void topo(int node){
   for (int i=1; i<=N; ++i){
      if (!dad[i].empty()){
         dad[i].erase(node);
         if (dad[i].empty()){
            ret.emplace_back(i);
            topo(i);
         }
      }
   }
}
 
int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int A;
   cin >> N >> A;
   for (int i=0; i<A; ++i){
      int a,b;
      cin >> a >> b;
      dad[b].emplace(a);
   }
   vector<int> cand;
   for (int i=1; i<=N; ++i){
      if (dad[i].empty()){
         ret.emplace_back(i);
         cand.emplace_back(i);
      }
   }
   for (auto& pos:cand) topo(pos);
   if (ret.size() != N) cout << -1;
   else{
      for (auto& i:ret) cout << i << ' ';
   }
   return 0;
}