Kosaraju's algorithm

kosaraju.cc

#include <vector>
#include <stack>
#include <iostream>

using namespace std;

int main() {
  vector<vector<int>> graph{
    {2, 3},
    {0},
    {1},
    {4},
    {}
  };
  vector<int> visited(graph.size());
  stack<int> _stack;

  // first dfs and whenever any vertex is finished, push it to the stack
  function<void(int)> dfs = [&dfs, &graph, &visited, &_stack](int curr) {
    if (visited[curr]) return;
    visited[curr] = 1;
    for (int next : graph[curr]) {
      if (!visited[next]) dfs(next);
    }
    _stack.push(curr);
  };
  for (int i = 0; i < graph.size(); i++) {
    if (!visited[i]) dfs(i);
  }

  // reversed graph
  vector<vector<int>> reversedGraph(graph.size());
  for (int i = 0; i < graph.size(); i++) {
    for (auto v : graph[i]) {
      reversedGraph[v].push_back(i);
    }
  }
  fill(visited.begin(), visited.end(), 0);

  function<void(int)> dfs2 = [&dfs2, &reversedGraph, &visited, &_stack](int curr) {
    if (visited[curr]) return;
    visited[curr] = 1;
    for (int next : reversedGraph[curr]) {
      if (!visited[next]) dfs2(next);
    }
    cout << curr << " ";
  };
  while (!_stack.empty()) {
    auto curr = _stack.top();
    if (!visited[curr]) {
      cout << "Strongly connected components: ";
      dfs2(curr);
      cout << endl;
    }
    _stack.pop();
  }
  return 0;
}

The example graph is taken from GeeksForGeeks