Saturday 19 March 2016

queue implementation of toposort

#include<bits/stdc++.h>
using namespace std;
vector<int>li[1000000];
int vis[1000000];
vector<int> ans;
int   n,m;
int deg[1000000];


int toposort()
 {
  queue<int> q ;
      for(int i=1;i<=n;i++)
           {
           if(deg[i]==0)
             {
               q.push(i);
           }
                  }
                 
                  while(!q.empty())
                  {
                  int node=q.front();
                  ans.push_back(node);
                  q.pop();
                  vis[node]=1;
                    vector<int>:: iterator it;
                    for(it=li[node].begin();it!=li[node].end();it++)
                      {
                        if(deg[*it]!=0)
                        {
                        deg[*it]--;
                        if(deg[*it]==0)
                            {
                            q.push(*it);
 }
 }
}
                   
 }
 
 }


int main()
{

 cin>>n>>m;
 for(int i=0;i<m;i++)
 {
  int a,b;
  cin>>a>>b;
  li[a].push_back(b);
  }
 
    toposort();
    for(int i=0;i<n;i++) cout<<ans[i]<<" ";
 
}

No comments:

Post a Comment