• API
• FAQ
• Tools
• Archive
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.

Top