Example: DFS-based Topological Sort in C++

// DFS-based Topological Sort
#include <iostream>
#include <vector>
#include <stack>
#include <list> // For adjacency list

using namespace std;

// Graph class to represent a directed graph
class Graph {
    int V; // Number of vertices
    list<int>* adj; // Pointer to an array containing adjacency lists

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& Stack) {
        // Mark the current node as visited
        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                topologicalSortUtil(neighbor, visited, Stack);
            }
        }

        // Push current vertex to stack which stores result
        Stack.push(v);
    }

public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

    // Function to add an edge to graph
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    // Prints a topological sort of the complete graph
    void topologicalSort() {
        stack<int> Stack;
        vector<bool> visited(V, false); // Mark all the vertices as not visited

        // Call the recursive helper function for all vertices
        // to get topological sort
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, Stack);
            }
        }

        // Print contents of stack
        cout << "Topological Sort (DFS-based): ";
        while (!Stack.empty()) {
            cout << Stack.top() << " ";
            Stack.pop();
        }
        cout << endl;
    }
};

int main() {
    // Step 1: Create a graph
    Graph g(6); // 6 vertices (0 to 5)

    // Step 2: Add edges representing dependencies
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    // Step 3: Perform topological sort
    g.topologicalSort();

    return 0;
}