Kosaraju: Difference between revisions
→{{header|C sharp|C#}}
Line 7:
;References:
* 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#}}==
| |||