TOPOLOGICAL GRAPH IN C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Function to perform DFS on a vertex
void topologicalSortUtil(int node, vector<bool>& visited, stack<int>& result, vector<vector<int>>& adj) {
    visited[node] = true; // Mark the current node as visited
    
    // Visit all adjacent vertices (neighbors) of the current node
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            topologicalSortUtil(neighbor, visited, result, adj); // Recursively perform DFS
        }
    }
    
    // After visiting all neighbors, push the current node onto the stack
    // This ensures that the node is added after all its dependencies
    result.push(node);
}

// Function to perform Topological Sort on the graph
void topologicalSort(int vertices, vector<vector<int>>& adj) {
    vector<bool> visited(vertices, false); // To keep track of visited nodes
    stack<int> result; // To store the topological order (nodes are pushed here)
    
    // Perform DFS for every unvisited node
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, visited, result, adj); // Perform DFS for the node
        }
    }
    
    // Print the topological order (from stack)
    cout << "Topological Sort: ";
    while (!result.empty()) {
        cout << result.top() << " "; // Output nodes in topological order
        result.pop();
    }
    cout << endl;
}

// Main function
int main() {
    int vertices = 6; // Number of vertices in the graph
    vector<vector<int>> adj(vertices); // Adjacency list representation of the graph
    
    // Add edges to the graph
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    
    // Call the topological sort function
    topologicalSort(vertices, adj);
    
    return 0;
}