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;
}