spider68

Topology sort

May 24th, 2020
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. void topology(stack<int>&s,int i,bool vis[],vector<int>adj[])
  2. {
  3.     vis[i]=true;
  4.     for(int j =0 ;j<adj[i].size();j++)
  5.     {
  6.         if(!vis[adj[i][j]])
  7.         topology(s,adj[i][j],vis,adj);
  8.     }
  9.     s.push(i);
  10. }
  11. int* topoSort(int V, vector<int> adj[]) {
  12.     bool vis[V]={false};
  13.     stack<int>s;
  14.     for(int i=0;i<V;i++)
  15.     {
  16.         if(!vis[i]){
  17.             topology(s,i,vis,adj);
  18.         }
  19.     }
  20.     int *a = ((int*)malloc(sizeof(int)*V));
  21.     int j=0;
  22.     while(!s.empty())
  23.     {
  24.         a[j++]=s.top();
  25.         s.pop();
  26.     }
  27.     return a;
  28. }
Add Comment
Please, Sign In to add comment