Topological Sorting Problem[Microsoft,Flipkart,Amazon]

Problem:Given a directed graph you need to complete the function topoSort which returns an array having the topologically sorted elements of the array and takes two arguments.

//http://www.practice.geeksforgeeks.org/problem-page.php?pid=700255
/* You need to complete this function */
int * topoSort(vector<int> graph[], int N)
{
   // Your code here
   vector<int> indeg(N,0);
   int *arr=(int*)malloc(sizeof(int)*N);
   queue<int> cue;
   int u,v;
   int idx=0;
   for(int i=0;i<N;i++)
   {
       for(int j=0;j<graph[i].size();j++)
       {
           indeg[graph[i][j]]+=1;
       }
   }

   for(int i=0;i<N;i++)
   {
       if(indeg[i]==0)
       cue.push(i);
   }
   while(cue.size())
   {
       u=cue.front();
       cue.pop();
       arr[idx++]=u;
       for(int i=0;i<graph[u].size();i++)
       {
           v=graph[u][i];
           indeg[v]-=1;
           if(indeg[v]==0)
           cue.push(v);
       }
   }
  return arr;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *