8.md

Topological Sort

METHOD 1(DFS)

	void dfs(int i,vector<int>& vis,vector<int> adj[],stack<int>& q)
	{
	    vis[i]=1;
	    for(auto it: adj[i])
	    {
	        if(!vis[it])
	            dfs(it,vis,adj,q);
	    }
	    q.push(i);
	    
	}
	vector<int> topoSort(int V, vector<int> adj[]) 
	{
	    // code here
	    
	    vector<int>vis(V,0);
	    stack<int>q;
	    
	    for(int i=0;i<V;i++)
	        if(!vis[i])
	            dfs(i,vis,adj,q);
	            
	   vector<int> ans;
	   while(!q.empty())
	   {
	       ans.push_back(q.top());
	       q.pop();
	   }
	   return ans;
	}

METHOD 2(BFS - kahn's Algo)

vector<int> topoSort(int V, vector<int> adj[]) 
	{
	    // code here
	    
	    int indegree[V]={0};
	    
	    for(int i=0;i<V;i++)
	        for(auto it: adj[i])
	            indegree[it]++;
	            
	   queue<int> q;
	   
	   for(int i=0;i<V;i++)
	        if(indegree[i]==0)
	            q.push(i);
	            
	   vector<int> ans;
	   
	   while(!q.empty())
	   {
	       int node=q.front();
	       q.pop();
	       ans.push_back(node);
	       
	       for(auto it:adj[node])
	       {
	           indegree[it]--;
	           if(indegree[it]==0)
	                q.push(it);
	       }
	       
	   }
	   
	   return ans;
	    
	}