9. Kosaraju's

Kosaraju's Algorithm is the standard algorithm to find the Strongly Connected Components (SCCs) in a directed graph.

Use Kruskal's when

• Graph is given as an edge list.
• Union-Find (DSU) is allowed.
• You need to detect cycles efficiently.

class Solution {

public:

    // First DFS
    void dfs1(int node,
              vector<vector<int>>& adj,
              vector<bool>& visited,
              stack<int>& st) {

        visited[node] = true;

        for (int neighbor : adj[node]) {

            if (!visited[neighbor])
                dfs1(neighbor, adj, visited, st);
        }

        // Store node according to finishing time
        st.push(node);
    }

    // Second DFS
    void dfs2(int node,
              vector<vector<int>>& transpose,
              vector<bool>& visited) {

        visited[node] = true;

        for (int neighbor : transpose[node]) {

            if (!visited[neighbor])
                dfs2(neighbor, transpose, visited);
        }
    }

    int kosaraju(int V, vector<vector<int>>& adj) {

        stack<int> st;

        vector<bool> visited(V, false);

        // STEP 1:
        // Store nodes in order of finishing time
        for (int i = 0; i < V; i++) {

            if (!visited[i])
                dfs1(i, adj, visited, st);
        }

        // STEP 2:
        // Reverse the graph
        vector<vector<int>> transpose(V);

        for (int u = 0; u < V; u++) {

            for (int v : adj[u]) {

                transpose[v].push_back(u);
            }
        }

        // STEP 3:
        // DFS according to stack order
        fill(visited.begin(), visited.end(), false);

        int sccCount = 0;

        while (!st.empty()) {

            int node = st.top();
            st.pop();

            if (!visited[node]) {

                dfs2(node, transpose, visited);

                sccCount++;
            }
        }

        return sccCount;
    }
};

If you need the actual SCCs (strongly connected components)

Store them

void dfs2(int node,
          vector<vector<int>>& transpose,
          vector<bool>& visited,
          vector<int>& component) {

    visited[node] = true;

    component.push_back(node);

    for (int neighbor : transpose[node]) {

        if (!visited[neighbor])
            dfs2(neighbor,
                 transpose,
                 visited,
                 component);
    }
}

Then

vector<vector<int>> SCCs;

while (!st.empty()) {

    int node = st.top();
    st.pop();

    if (!visited[node]) {

        vector<int> component;

        dfs2(node,
             transpose,
             visited,
             component);

        SCCs.push_back(component);
    }
}

After this SCCs contains every strongly connected components