kahn's algorithm
//Topological sort using BFS (Kahn's Algorithm) #include<bits/stdc++.h> using namespace std; void addedge(vector<int>adj[],int u,int v) { adj[u].push_back(v); } void toposort(vector<int>adj[],int n) { queue<int>q; vector<int>indegree(n,0); for(int i=0;i<n;i++) { for(auto it: adj[i]) { indegree[it]++; } } for(int i=0;i<n;i++) { if(indegree[i]==0) { q.push(i); } }vector<int>topo; while(!q.empty()) { int node=q.front(); q.pop(); topo.push_back(node); for(auto it:adj[node]) { indegree[it]--; if(indegree[it]==0) { q.push(it); } } } int si=topo.size(); for(int i=0;i<si;i++) { cout<<topo[i]<<" "; } } int main() { int vertex,edges; cout<<"Enter the number of vertex and edges:"<<endl; cin>>vertex>>edges; vector<int>adj[vertex]; int a,b; cout<<"Enter the links:"<<endl; for(int i=0;i<vertex;i++) { cin>>a>>b; addedge(adj,a,b); } // for(int i=0;i<vertex;i++) //{ toposort(adj,vertex); //} return 0; }
