Topological Sort

topologicalSort.cpp

int V = 6;    // No. of vertices
list<int> *adj = new list<int>[V];  // Pointer to an array containing adjacency list (adj[0]-adj[5])

void topologicalSortUtil(int v, bool visited[], stack<int>& s) 
{ 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    for (list<int>::iterator i = adj[v].begin(); i != adj[v].end(); ++i) 
        if (!visited[*i]) 
            topologicalSortUtil(*i, visited, s); 
  
    // Push current vertex to stack which stores result 
    s.push(v); 
} 
  
void topologicalSort() 
{ 
    stack<int> s; 
  
    // Mark all the vertices as not visited 
    bool* visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // Call the recursive helper function to store Topological 
    // Sort starting from all vertices one by one 
    for (int i = 0; i < V; i++) 
        if (visited[i] == false) 
            topologicalSortUtil(i, visited, s); 
  
    while (s.empty() == false) { 
        cout << s.top() << " "; 
        s.pop(); 
    }
}