Kosaraju: Difference between revisions
Content added Content deleted
Line 7: | Line 7: | ||
;References: |
;References: |
||
* The article on [[wp:Kosaraju's_algorithm|Wikipedia]]. |
* The article on [[wp:Kosaraju's_algorithm|Wikipedia]]. |
||
=={{header|C++}}== |
|||
{{trans|D}} |
|||
<lang cpp>#include <functional> |
|||
#include <iostream> |
|||
#include <ostream> |
|||
#include <vector> |
|||
template<typename T> |
|||
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { |
|||
auto it = v.cbegin(); |
|||
auto end = v.cend(); |
|||
os << "["; |
|||
if (it != end) { |
|||
os << *it; |
|||
it = std::next(it); |
|||
} |
|||
while (it != end) { |
|||
os << ", " << *it; |
|||
it = std::next(it); |
|||
} |
|||
return os << "]"; |
|||
} |
|||
std::vector<int> kosaraju(std::vector<std::vector<int>>& g) { |
|||
// 1. For each vertex u of the graph, mark u as unvisited. Let l be empty. |
|||
auto size = g.size(); |
|||
std::vector<bool> vis(size); // all false by default |
|||
std::vector<int> l(size); // all zero by default |
|||
auto x = size; // index for filling l in reverse order |
|||
std::vector<std::vector<int>> t(size); // transpose graph |
|||
// Recursive subroutine 'visit': |
|||
std::function<void(int)> visit; |
|||
visit = [&](int u) { |
|||
if (!vis[u]) { |
|||
vis[u] = true; |
|||
for (auto v : g[u]) { |
|||
visit(v); |
|||
t[v].push_back(u); // construct transpose |
|||
} |
|||
l[--x] = u; |
|||
} |
|||
}; |
|||
// 2. For each vertex u of the graph do visit(u) |
|||
for (int i = 0; i < g.size(); ++i) { |
|||
visit(i); |
|||
} |
|||
std::vector<int> c(size); // used for component assignment |
|||
// Recursive subroutine 'assign': |
|||
std::function<void(int, int)> assign; |
|||
assign = [&](int u, int root) { |
|||
if (vis[u]) { // repurpose vis to mean 'unassigned' |
|||
vis[u] = false; |
|||
c[u] = root; |
|||
for (auto v : t[u]) { |
|||
assign(v, root); |
|||
} |
|||
} |
|||
}; |
|||
// 3: For each element u of l in order, do assign(u, u) |
|||
for (auto u : l) { |
|||
assign(u, u); |
|||
} |
|||
return c; |
|||
} |
|||
std::vector<std::vector<int>> g = { |
|||
{1}, |
|||
{2}, |
|||
{0}, |
|||
{1, 2, 4}, |
|||
{3, 5}, |
|||
{2, 6}, |
|||
{5}, |
|||
{4, 6, 7}, |
|||
}; |
|||
int main() { |
|||
using namespace std; |
|||
cout << kosaraju(g) << endl; |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |