Topological sort using DFS without recursion

I think your code is a good non-recursive DFS . The key point of topological sort is that:

When you pick a node to push into the stack. This node must have no precessor( has a in-degree of 0). This means you are doing a DFS base on in-degree in stead of push all the adjacent nodes into the stack, you always pick the one with 0 in-degree

So you push every node that have no precessor in the stack. Pop one, print it and remove it from all its adjacent nodes' precessor list ( or decrease its adjacent nodes' in-degree by 1). This need you to edit your adjacent list. Than push all its adjacent nodes that has in-degree of 0 now in to the stack( this phase may fail but no problem, you still got some nodes in the stack). Then pop the next one. Repeat until the stack is empty. The node sequence that you printed is the topological sort result of the graph.

In order to construct the postOrder list you need to know the time when your algorithm has finished processing the last child of node k.

One way to figure out when you have popped the last child off the stack is to put special marks on the stack to indicate spots where the children of a particular node are starting. You could change the type of your dfs stack to vector<pair<bool,int>>. When the bool is set to true, it indicates a parent; false indicates a child.

When you pop a "child pair" (i.e. one with the first member of the pair set to false) off the stack, you run the code that you currently have, i.e. push all their children onto the stack with your for loop. Before entering the for loop, however, you should push make_pair(true, node) onto the stack to mark the beginning of all children of this node.

When you pop a "parent pair" off the stack, you push the parent index onto the postOrder, and move on:

vector<vector<int> > graph;
vector<bool> visited(max);
stack<pair<bool,int>> dfs;
stack<int> postOrder;
for(int i=0 ; i < max ; i++){
    if(!visited[i]){
        dfs.push(make_pair(false,i));
    }   
    while(!dfs.empty()){
        pair<bool,int> node=dfs.top();
        dfs.pop();
        if (node.first) {
            postOrder.push(node.second);
            continue;
        }
        if (visited[node.second]) {
            continue;
        }
        visited[node.second]=true;
        dfs.push(make_pair(true, node.second));
        const auto& newVec=graph[node.second]; //vector of neighboors
        for(const auto son: newVec){
            if(!visited[son]){
                dfs.push(make_pair(false, son));
            }
        }
    }
}

Demo on ideone.

Iterative topological sort. Using stack and colorizing graph nodes: 0 - not visited, 1 - in progress, 2 - done. With built-in check whether graph has cycles or not. This approach doesn`t need extra states ("anchors") in stack (like in this solution) with info about should we add current node to the answer or not.

Try sample.

void dfs(const unordered_multimap<int, int>& graph, vector<int>& color, int node, const function<void(int)> post_order_func)
{
  stack<int> nodes;
  nodes.push(node);

  while (!nodes.empty())
  {
    int from = nodes.top();

    if (color[from] == 1)
    {
      color[from] = 2;
      post_order_func(from);
      nodes.pop();
      continue;
    }
    else if (color[from] == 2)
    {
      nodes.pop();
      continue;
    }

    color[from] = 1;
    auto range = graph.equal_range(from);

    for (auto it = range.first; it != range.second; ++it)
    {
      const auto& to = it->second;
      if (color[to] == 0)
      {
        nodes.push(to);
      }
      else if (color[to] == 1)
      {
        throw runtime_error("Graph has cycle. Topological sort impossible.");
      }
    }
  }
}

void topological_sort(int n, const unordered_multimap<int, int>& graph, vector<int>& result)
{
  result.resize(n);

  vector<int> color(n, 0);
  int j = 0;
  auto post_order_func = [&result, &j](int node) {
    result[j++] = node;
  };

  for (int i = 0; i < n; ++i)
  {
    if (color[i] == 0)
    {
      dfs(graph, color, i, post_order_func);
    }
  }

  reverse(begin(result), end(result));
}