Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
902 B
1
Indexable
Never
#include<vector>
#include<queue>
//vector faster than map
 
//kahns algo
vector<int> topologicalSort(vector<vector<int>> &edges, int v, int e)  {
    vector<vector<int>> adjlist(v); //making adj list
    for(int i=0;i<e;i++){   //edges.size()
        int x=edges[i][0];
        int y=edges[i][1];
        adjlist[x].push_back(y);
       // adjlist[y].push_back(x);

    }
    vector<bool> vis(v);
    queue<int> q;
    vector<int> ans;
    vector<int>degree(v);
    for(auto i:adjlist){
        for (auto j:i){
            degree[j]++;
        }
    }
    for(int i=0;i<v;i++){
        if(degree[i]==0) q.push(i);
    }
    while(!q.empty()){
        int front= q.front();
        q.pop();
        ans.push_back(front);
        for(auto nbr:adjlist[front]){
            degree[nbr]--;
            if(degree[nbr]==0) q.push(nbr);
        }
    }
    return ans;

}