Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
822 B
2
Indexable
Never
    public:
	//Function to return list containing vertices in Topological order. 
	vector<int> topoSort(int V, vector<int> adj[]) 
	{
	    bool visited[V] = {false};
	    stack<int> st;
	    
	    for (int i = 0; i < V; i++) {
	        if (!visited[i])
	            dfs(i, adj, st, visited);
	    }
	    
	    
	    vector<int> topoOrder;
	    while (!st.empty()) {
	        topoOrder.push_back(st.top());
	        st.pop();
	    }
	    
	   return topoOrder;
	}
	
    private:
    void dfs(int node, vector<int> adj[], stack<int> &st, bool visited[]) {
        if (visited[node]) return;
        
        visited[node] = true;
        for (int i = 0; i < adj[node].size(); i++)
            if (!visited[adj[node][i]])
                dfs(adj[node][i], adj, st, visited);
                
        st.push(node);
    }