88 lines
2.0 KiB
C++
88 lines
2.0 KiB
C++
#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;
|
|
}
|