Topological sort

Problem Statement - link #

Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph.

Your Task: You don’t need to read input or print anything. Your task is to complete the function topoSort() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns an array consisting of a the vertices in Topological order. As there are multiple Topological orders possible, you may return any of them. If your returned topo sort is correct then console output will be 1 else 0.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:

Output:
1
Explanation:
The output 1 denotes that the order is
valid. So, if you have, implemented
your function correctly, then output
would be 1 for all test cases.
One possible Topological order for the
graph is 3, 2, 1, 0.

Constraints #

• 2 ≤ V ≤ 10^4
• 1 ≤ E ≤ (N*(N-1))/2

Solutions #

class Solution
{
    public:
	void DFSUtil(int s, vector<int> adj[], bool vis[], stack<int> &st){
	    vis[s]=1;
	    for(int i: adj[s])
	        if(!vis[i])
	            DFSUtil(i,adj,vis,st);
	    st.push(s);
	     
	}
	//Function to return list containing vertices in Topological order. 
	vector<int> topoSort(int V, vector<int> adj[]) 
	{
	    // code here
	    vector<int> res;
	    stack<int> st;
	    bool vis[V]={0};
	    for(int i=0;i<V;i++)
	        if(!vis[i])
	            DFSUtil(i,adj,vis,st);
	    while(!st.empty()){
	        res.push_back(st.top());
	        st.pop();
	    }
	    return res;
	}
};