SHARE
TWEET

Topological sort

keverman Jan 12th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // For connected graphs
  2. std::vector<int> topological_sort()
  3. {
  4.     std::vector<std::vector<int>> reversed_edges(size());
  5.     std::vector<int> degree(size()), sorted;
  6.     std::queue<int> Q;
  7.  
  8.     for(int from = 0; from < size(); from++)
  9.         for(int to : edges[from])
  10.             reversed_edges[to].push_back(from);
  11.  
  12.     for(int i = 0; i < size(); i++)
  13.         if((degree[i] = reversed_edges[i].size()) == 0)
  14.             Q.push(i);
  15.  
  16.     while(!Q.empty())
  17.     {
  18.         int from = Q.front();
  19.         Q.pop();
  20.  
  21.         sorted.push_back(from);
  22.  
  23.         for(int to : edges[from])
  24.             if(--degree[to] == 0)
  25.                 Q.push(to);
  26.     }
  27.  
  28.     return sorted;
  29. }
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