daily pastebin goal
49%
SHARE
TWEET

Kosaraju's Algorithm

keverman Feb 11th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Kosaraju's algorithm for strongly connected components in a directed graph
  2. // Requires use of an appropriate graph class
  3.  
  4. std::vector<std::vector<int>> reverse_edges()
  5. {
  6.     std::vector<std::vector<int>> reversed_edges(size());
  7.    
  8.     for(int from = 0; from < size(); from++)
  9.         for(int to : edges[from])
  10.             reversed_edges[to].push_back(from);
  11.        
  12.     return reversed_edges;
  13. }
  14.  
  15. void post_order(int from, std::vector<bool> &visited, std::stack<int> &S)
  16. {
  17.     visited[from] = true;
  18.    
  19.     for(int to : edges[from])
  20.         if(!visited[to])
  21.             post_order(to, visited, S);
  22.        
  23.     S.push(from);
  24. }
  25.  
  26. std::vector<std::vector<int>> Kosaraju()
  27. {
  28.     std::vector<std::vector<int>> reversed_edges = reverse_edges();
  29.     std::vector<std::vector<int>> components;
  30.     std::vector<bool> visited(size(), false);
  31.     std::stack<int> S;
  32.    
  33.     for(int vertex = 0; vertex < size(); vertex++)
  34.         if(!visited[vertex])
  35.             post_order(vertex, visited, S);
  36.        
  37.     std::fill(visited.begin(), visited.end(), false);
  38.    
  39.     while(!S.empty())
  40.     {
  41.         int cur = S.top();
  42.         S.pop();
  43.        
  44.         if(!visited[cur])
  45.         {
  46.             std::vector<int> component;
  47.             std::queue<int> Q;
  48.            
  49.             Q.push(cur);
  50.             visited[cur] = true;
  51.            
  52.             while(!Q.empty())
  53.             {
  54.                 int from = Q.front();
  55.                 component.push_back(from);
  56.                 Q.pop();
  57.                
  58.                 for(int to : reversed_edges[from])
  59.                 {
  60.                     if(!visited[to])
  61.                     {
  62.                         Q.push(to);
  63.                         visited[to] = true;
  64.                     }
  65.                 }
  66.             }
  67.            
  68.             components.push_back(component);
  69.         }
  70.     }
  71.    
  72.     return components;
  73. }
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