1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

class Graph 
{
private:
    std::unordered_map<int, std::vector<int>> adjList;

public:
    void addEdge(int u, int v) 
    {
        adjList[u].push_back(v);
    }

    void topologicalSortUtil(int v, std::unordered_map<int, bool>& visited, std::stack<int>& stack) 
    {
        visited[v] = true;

        for (int i : adjList[v]) 
        {
            if (!visited[i])
            {
                topologicalSortUtil(i, visited, stack);
            }
        }

        stack.push(v);
    }

    void topologicalSort() 
    {
        std::unordered_map<int, bool> visited;
        std::stack<int> stack;

        // Initialize all vertices as not visited
        for (auto& pair : adjList)
        {
            visited[pair.first] = false;
        }

        for (auto& pair : adjList) 
        {
            int vertex = pair.first;
            if (!visited[vertex]) 
            {
                topologicalSortUtil(vertex, visited, stack);
            }
        }

        // Print contents of the stack
        std::cout << "Topological sorting order: ";
        while (!stack.empty()) 
        {
            std::cout << stack.top() << " ";
            stack.pop();
        }
        std::cout << std::endl;
    }
};

int main() 
{
    Graph dag;

    dag.addEdge(5, 2);
    dag.addEdge(5, 0);
    dag.addEdge(4, 0);
    dag.addEdge(4, 1);
    dag.addEdge(2, 3);
    dag.addEdge(3, 1);

    dag.topologicalSort();

    return 0;
}