Saturday 19 March 2016

stack implementation

#include<bits/stdc++.h>
using namespace std;
vector<int>li[1000000];
int vis[1000000];
vector<int> ans;
int toposort(int start,stack<int> &s,int vis[])
 {
  vector<int>:: iterator it;
  for(it=li[start].begin();it!=li[start].end();it++)
  {
  if(!vis[*it])
  {
 
   vis[*it]=1;
   toposort(*it,s,vis);
}
}

s.push(start);
 
 }


int main()
{
int   n,m;
 cin>>n>>m;
 for(int i=0;i<m;i++)
 {
  int a,b;
  cin>>a>>b;
  li[a].push_back(b);
  }
 
  stack<int> s;
  for(int i=1;i<=n;i++)
  {
  if(!vis[i])
    {
    vis[i]=1;
     toposort(i,s,vis);
  }
  }
  while(!s.empty())
   {
    ans.push_back(s.top());
    s.pop();
   }
   for(int i=n-1;i>=0;i--) cout<<ans[i]<<" ";
 
}

No comments:

Post a Comment