Topological sort | Practice | GeeksforGeeks

PHOTO EMBED

Thu Jun 01 2023 08:04:01 GMT+0000 (Coordinated Universal Time)

Saved by @DxBros #c++ #kahns

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

This is topological sort using Kahn's algorithm

https://practice.geeksforgeeks.org/problems/topological-sort/1