topological sort

1int n; // number of vertices
2vector<vector<int>> adj; // adjacency list of graph
3vector<bool> visited;
4vector<int> ans;
5
6void dfs(int v) {
7    visited[v] = true;
8    for (int u : adj[v]) {
9        if (!visited[u])
10            dfs(u);
11    }
12    ans.push_back(v);
13}
14
15void topological_sort() {
16    visited.assign(n, false);
17    ans.clear();
18    for (int i = 0; i < n; ++i) {
19        if (!visited[i])
20            dfs(i);
21    }
22    reverse(ans.begin(), ans.end());
23}
24

1L ← Empty list that will contain the sorted nodes
2while exists nodes without a permanent mark do
3    select an unmarked node n
4    visit(n)
5
6function visit(node n)
7    if n has a permanent mark then
8        return
9    if n has a temporary mark then
10        stop   (not a DAG)
11
12    mark n with a temporary mark
13
14    for each node m with an edge from n to m do
15        visit(m)
16
17    remove temporary mark from n
18    mark n with a permanent mark
19    add n to head of L
20

1void dfs_helper(T src, map<int,bool>& visited, list<T> &ordering) { 
2    //Recursive function that will traverse the graph 
3         
4    visited[src] = true; 
5    //go to all nbr of that node that is not visited 
6    for(T nbr:l[src]) { 
7        if(!visited[nbr]) { 
8            dfs_helper(src,visited,ordering);
9        } 
10    } 
11    ordering.push_front(src);
12} 
13
14int dfs(T src) { 
15        map<int,bool> visited; 
16        list<T> ordering;
17        //Mark all nodes as not visited. 
18        //l = adjacency list implemented using std::unordered_map
19        for(auto p:l) { 
20            T node = p.first; 
21            visited[node] = false; 
22        } 
23
24        for(auto p:l) {
25            T node = p.first;
26            if(!visited[node]) {
27                dfs_helper(node,visited,ordering);
28            }
29        }
30
31        //Finally print the list
32        for(auto node:ordering) {
33            cout << node << endl;
34        }
35}

1def topological_sort():
2    for each node:
3        if visited[node] is False:
4            dfs(node)
5def dfs(node):
6    visited[node] = True
7    for nei in neighbours[node]:
8        dfs(node)
9    ret.insert_at_the _front(node)