Problem 17 : Kahn's Algorithm | Topological Sort Algorithm | BFS|C++

 

Kahn's Algorithm | Topological Sort Algorithm | BFS|C++

By Ujjal Roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

const ll N=1000;

stack<ll>st;

vector<ll>adj[N];

ll vis[N];

// dfs function is another away to implement toposort

/*void dfs(ll node)

{

     vis[node]=1;

     for(ll i=0;i<adj[node].size();i++)

     {

         ll child;

         child=adj[node][i];

         if(vis[child]==0)

         {

             dfs(child);

         }

     }

     st.push(node);

}*/

int main()

{

    cout<<"Enter number node and edge : ";

    ll node,edge;

    cin>>node>>edge;

     ll indeg[node];

    memset(indeg,0,sizeof(indeg));

    while(edge--)

    {

        ll u,v;

        cin>>u>>v;

        adj[u].push_back(v);

        indeg[v]++;

       // adj[v].push_back(u);

    }

 queue<ll>q;

  for(ll i=0;i<node;i++)

  {

      if(indeg[i]==0)

      {

          q.push(i);

      }

  }

  vector<int>v;

    while(!q.empty())

    {

        ll node1=q.front();

        q.pop();

        v.push_back(node1);

        for(auto u:adj[node1])

        {

            indeg[u]--;

            if(indeg[u]==0)

            {

                q.push(u);

            }

        }

    }

    for(ll i=0;i<v.size();i++)

    {

        cout<<v[i]<<" ";

    }

}