Advertisement
keverman

Kosaraju's algorithm

Feb 9th, 2020
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. int V;
  2. vector<vector<int>> edges, sccs;
  3. vector<bool> visited;
  4. stack<int> S;
  5.  
  6. void post_order(int u)
  7. {
  8.     if (!visited[u])
  9.     {
  10.         visited[u] = true;
  11.         for (int v : edges[u])
  12.             post_order(v);
  13.         S.push(u);
  14.     }
  15. }
  16.  
  17. void Kosaraju()
  18. {
  19.     vector<vector<int>> rev_edges(V);
  20.     visited.assign(V, false);
  21.  
  22.     for (int u = 0; u < V; u++)
  23.     {
  24.         post_order(u);
  25.         for (int v : edges[u])
  26.             rev_edges[v].push_back(u);
  27.     }
  28.  
  29.     visited.assign(V, false);
  30.     while (!S.empty())
  31.     {
  32.         int src = S.top(); S.pop();
  33.  
  34.         if (!visited[src])
  35.         {
  36.             queue<int> Q({ src });
  37.             visited[src] = true;
  38.             sccs.push_back({});
  39.  
  40.             while (!Q.empty())
  41.             {
  42.                 int u = Q.front(); Q.pop();
  43.                 sccs.back().push_back(u);
  44.  
  45.                 for (int v : rev_edges[u])
  46.                     if (!visited[v])
  47.                         Q.push(v), visited[v] = true;
  48.             }
  49.         }
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement