# Description:

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

## Example:

``````Note
``````

# Idea:

Method 1: (DFS)

``````L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)

function visit(node n)
if n has a permanent mark then return
if n has a temporary mark then stop (not a DAG)
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
``````

# Code:

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

bool visit(int key, const unordered_map<int, unordered_set<int>>& graph,
unordered_map<int, int>& hashMap, vector<int>& sortedElem){
if(hashMap[key]==2) return true;
if(hashMap[key]==1) return false;
hashMap[key]=1;
auto iter = graph.find(key);
for(auto elem: iter->second){
visit(elem, graph, hashMap, sortedElem);
}
hashMap[key]=2;
sortedElem.push_back(key);
return true;
}

vector<int> topoSort(const unordered_map<int, unordered_set<int>>& graph){
unordered_map<int, int> hashMap;
// Mark: 0 unvisited; 1 temporary; 2 permantly
for(auto elem: graph){
hashMap[elem.first]=0;
}

vector<int> sortedElem;
for(auto elem: graph){
if(hashMap[elem.first]==0){
visit(elem.first, graph, hashMap, sortedElem);
}
}

reverse(sortedElem.begin(), sortedElem.end());
return sortedElem;
}

int main(){
unordered_map<int, unordered_set<int>> graph;
graph[5].insert(0);
graph[5].insert(2);
graph[4].insert(0);
graph[4].insert(1);
graph[2].insert(3);
graph[3].insert(1);
graph[0]=unordered_set<int>();
graph[1]=unordered_set<int>();

for(auto elem: topoSort(graph)){
cout<<elem<<' ';
}
}
``````