daily pastebin goal
62%
SHARE
TWEET

Topological Sort

keverman Jan 17th, 2018 (edited) 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. std::vector<int> TopologicalSort(std::vector<int> *edgesBegs, std::vector<int> *edgesEnds, int V = V)
  2. {
  3.     int vertexDegree[V];
  4.     std::vector<int> topologicalOrder;
  5.     std::queue<int> Q;
  6.  
  7.     for(int i = 0; i < V; i++)
  8.     {
  9.         vertexDegree[i] = edgesEnds[i].size();
  10.  
  11.         if(vertexDegree[i] == 0)
  12.             Q.push(i);
  13.     }
  14.  
  15.     while(!Q.empty())
  16.     {
  17.         int from = Q.front();
  18.         Q.pop();
  19.         topologicalOrder.push_back(from);
  20.  
  21.         for(unsigned int i = 0; i < edgesBegs[from].size(); i++)
  22.         {
  23.             int to = edgesBegs[from][i];
  24.             vertexDegree[to]--;
  25.  
  26.             if(vertexDegree[to] == 0)
  27.                 Q.push(to);
  28.         }
  29.     }
  30.  
  31.     return topologicalOrder;
  32. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top