Kosaraju's Algorithm

#include <stdbool.h>
#define V 5

bool visited[V];
int stack[V], top = -1;

/* Pass 1: DFS on original graph, push finish order */
void dfs1(int graph[V][V], int v) {
    visited[v] = true;
    for (int i = 0; i < V; i++)
        if (graph[v][i] && !visited[i]) dfs1(graph, v);
    stack[++top] = v;
}

/* Pass 2: DFS on transposed graph */
void dfs2(int trans[V][V], int v, int comp[]) {
    visited[v] = true; comp[v] = top;
    for (int i = 0; i < V; i++)
        if (trans[v][i] && !visited[i]) dfs2(trans, i, comp);
}

void kosaraju(int graph[V][V], int trans[V][V], int comp[]) {
    for (int i = 0; i < V; i++) { visited[i] = false; }
    for (int i = 0; i < V; i++) if (!visited[i]) dfs1(graph, i);
    for (int i = 0; i < V; i++) { visited[i] = false; }
    while (top >= 0) {
        int v = stack[top--];
        if (!visited[v]) dfs2(trans, v, comp);
    }
}

#include <vector>
#include <stack>
#include <algorithm>

void dfs1(const std::vector<std::vector<int>>& adj,
          std::vector<bool>& visited, std::stack<int>& stk, int v) {
    visited[v] = true;
    for (int u : adj[v]) if (!visited[u]) dfs1(adj, visited, stk, u);
    stk.push(v);
}

void dfs2(const std::vector<std::vector<int>>& radj,
          std::vector<bool>& visited, std::vector<int>& comp, int v, int id) {
    visited[v] = true; comp[v] = id;
    for (int u : radj[v]) if (!visited[u]) dfs2(radj, visited, comp, u, id);
}

int kosaraju(const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::stack<int> stk;
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(adj, visited, stk, i);

    // Build reversed graph
    std::vector<std::vector<int>> radj(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) radj[v].push_back(u);

    std::fill(visited.begin(), visited.end(), false);
    std::vector<int> comp(n);
    int num_scc = 0;
    while (!stk.empty()) {
        int v = stk.top(); stk.pop();
        if (!visited[v]) { dfs2(radj, visited, comp, v, num_scc); num_scc++; }
    }
    return num_scc;
}

import java.util.*;

public static int kosaraju(List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs1(adj, visited, stack, i);

    // Build reversed graph
    List<List<Integer>> radj = new ArrayList<>();
    for (int i = 0; i < n; i++) radj.add(new ArrayList<>());
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) radj.get(v).add(u);

    Arrays.fill(visited, false);
    int[] comp = new int[n]; int numSCC = 0;
    while (!stack.isEmpty()) {
        int v = stack.pop();
        if (!visited[v]) { dfs2(radj, visited, comp, v, numSCC++); }
    }
    return numSCC;
}
private static void dfs1(List<List<Integer>> adj, boolean[] vis,
                          Deque<Integer> stk, int v) {
    vis[v] = true;
    for (int u : adj.get(v)) if (!vis[u]) dfs1(adj, vis, stk, u);
    stk.push(v);
}
private static void dfs2(List<List<Integer>> radj, boolean[] vis,
                          int[] comp, int v, int id) {
    vis[v] = true; comp[v] = id;
    for (int u : radj.get(v)) if (!vis[u]) dfs2(radj, vis, comp, u, id);
}

def kosaraju(adj: list[list[int]]) -> int:
    n       = len(adj)
    visited = [False] * n
    order   = []

    def dfs1(v: int) -> None:
        visited[v] = True
        for u in adj[v]:
            if not visited[u]: dfs1(u)
        order.append(v)

    for i in range(n):
        if not visited[i]: dfs1(i)

    # Build reversed graph
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]: radj[v].append(u)

    visited[:] = [False] * n
    comp = [-1] * n; num_scc = 0

    def dfs2(v: int, scc_id: int) -> None:
        visited[v] = True; comp[v] = scc_id
        for u in radj[v]:
            if not visited[u]: dfs2(u, scc_id)

    for v in reversed(order):
        if not visited[v]:
            dfs2(v, num_scc); num_scc += 1

    return num_scc

function kosaraju(adj) {
  const n       = adj.length;
  const visited = new Array(n).fill(false);
  const order   = [];

  function dfs1(v) {
    visited[v] = true;
    for (const u of adj[v]) if (!visited[u]) dfs1(u);
    order.push(v);
  }
  for (let i = 0; i < n; i++) if (!visited[i]) dfs1(i);

  // Build reversed graph
  const radj = Array.from({length: n}, () => []);
  for (let u = 0; u < n; u++)
    for (const v of adj[u]) radj[v].push(u);

  visited.fill(false);
  const comp = new Array(n).fill(-1);
  let numSCC = 0;

  function dfs2(v, id) {
    visited[v] = true; comp[v] = id;
    for (const u of radj[v]) if (!visited[u]) dfs2(u, id);
  }
  for (let i = n - 1; i >= 0; i--) {
    const v = order[i];
    if (!visited[v]) { dfs2(v, numSCC); numSCC++; }
  }
  return numSCC;
}