dsa/graphs/sorting/ | desc: topological ordering in DAG

topological ordering.cpp

#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> graph;

vector<int> bfs(){
  vector<int> indeg(N, 0);
  vector<int> ans;
  for (auto i : graph)
    for (auto j : i) indeg[j]++;
  queue<int> q;
  for (int i = 0; i < N; i++)
    if (indeg[i] == 0) q.push(i);
  while (!q.empty()) {
      int u = q.front();
      q.pop();
      ans.push_back(u);
      for (auto i : graph[u]) 
        if (--indeg[i] == 0) q.push(i);
  }
  return ans;
}