topological_sort.cc

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <utility>

using namespace std;

struct not_dag{};
vector<int> tsort(unordered_set<int> s, set<pair<int, int>> e) {
  vector<int> l;
  for (auto&& var : e) {
    s.erase(var.second);
  }
  while(!s.empty()) {
    int n = *s.begin();
    s.erase(s.begin());
    l.push_back(n);
    decltype(e.begin()) x;
    while((x = find_if(e.begin(), e.end(), [&](pair<int, int> y){return y.first == n;})) != e.end()){
      int z = x->second;
      e.erase(x);
      if (all_of(e.begin(), e.end(), [&](pair<int, int> y){return y.second != z;})) {
        s.insert(z);
      }
    }
  }

  if (!e.empty()){
    throw not_dag();
  }
  return l;
}

int main(int argc, char const* argv[])
{
  unordered_set<int> v = {2, 3, 5, 7, 8, 9, 10, 11};
  set<pair<int, int>> e;
  e.emplace(7, 11);
  e.emplace(7, 8);
  e.emplace(5, 11);
  e.emplace(3, 8);
  e.emplace(3, 10);
  e.emplace(11, 2);
  e.emplace(11, 9);
  e.emplace(11, 10);
  e.emplace(8, 9);
  e.emplace(2, 9);
  e.emplace(9, 10);
  for (auto&& var : tsort(v, e)) {
    std::cout << var << std::endl;
  }
  return 0;
}