Untitled
plain_text
a month ago
902 B
0
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; }