Kosaraju's Algorithm Without a Stack and Transposed Graph with 2 DFS passes using a queue

I was understanding this algorithm and found that this can be solved using this alternative approach of using only a single queue instead of stack and can eliminate the use of transposed graph which requires extra space and extra DFS time of complexity of O(V+E).

Idea

Kosaraju's algorithm is commonly presented with three DFS passes:

1. Run DFS on the original graph and push each vertex onto a stack when its DFS call finishes.
2. Reverse every edge to build the transposed graph.
3. Process vertices by popping the stack, running DFS on the transposed graph to identify strongly connected components (SCCs).

There is a useful alternative: enqueue each vertex when its first DFS finishes, then process the queue in FIFO order and run the second DFS on the original graph. This avoids both the stack and the transposed graph.

The important detail is that the queue must receive a vertex after all of its outgoing neighbours have been explored. Because a queue is FIFO, vertices are processed in increasing finishing-time order.

Why does it work?

Collapse every SCC into a single vertex. The resulting condensation graph is a directed acyclic graph (DAG).

For every edge from SCC A to SCC B in this DAG, the first DFS gives A a later finishing time than B. Therefore, vertices from sink SCCs are processed first by the FIFO queue.

A sink SCC has no outgoing edge to another SCC. So, when the second DFS starts from an unvisited vertex in a sink SCC and follows edges in the original graph, it cannot escape into a different SCC. It reaches all vertices in that SCC because the vertices inside an SCC are mutually reachable.

After that SCC is marked visited, later DFS traversals cannot absorb it into another component. Repeating this process identifies every SCC.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

class KosarajuQueue {
private:
    int n;
    vector<vector<int>> adj;
    vector<bool> visited;
    queue<int> order;
    vector<vector<int>> components;

    // First pass: enqueue each vertex after all descendants finish.
    void dfsOrder(int u) {
        visited[u] = true;

        for (int v : adj[u]) {
            if (!visited[v]) {
                dfsOrder(v);
            }
        }

        order.push(u);  // Enqueue at DFS completion time.
    }

    // Second pass: use the ORIGINAL graph.
    void dfsComponent(int u, vector<int>& component) {
        visited[u] = true;
        component.push_back(u);

        for (int v : adj[u]) {
            if (!visited[v]) {
                dfsComponent(v, component);
            }
        }
    }

public:
    explicit KosarajuQueue(int n)
        : n(n), adj(n), visited(n, false) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    vector<vector<int>> findSCCs() {
        // First DFS pass.
        for (int u = 0; u < n; ++u) {
            if (!visited[u]) {
                dfsOrder(u);
            }
        }

        // Reset visited before the second pass.
        fill(visited.begin(), visited.end(), false);

        // Second DFS pass: FIFO finishing order, original graph.
        while (!order.empty()) {
            int u = order.front();
            order.pop();

            if (!visited[u]) {
                vector<int> component;
                dfsComponent(u, component);
                components.push_back(component);
            }
        }

        return components;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;  // n vertices, m directed edges; vertices are 0-indexed

    KosarajuQueue solver(n);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        solver.addEdge(u, v);
    }

    vector<vector<int>> sccs = solver.findSCCs();

    cout << sccs.size() << '\\n';
    for (const auto& component : sccs) {
        for (int v : component) {
            cout << v << ' ';
        }
        cout << '\\n';
    }

    return 0;
}

Example

Input

4 4
0 1
1 2
2 1
2 3

This represents the edges:

• 0 -> 1
• 1 -> 2
• 2 -> 1
• 2 -> 3

Expected SCCs (the order of components and vertices within each component may vary):

3
3
1 2
0

The SCCs are {0}, {1, 2}, and {3}.

Complexity

• Time: O(V + E) — each vertex and edge is processed a constant number of times.
• Space: O(V + E) — adjacency lists, visited array, queue, and stored components.

Important notes

• Enqueue a vertex only after its DFS finishes; enqueueing it when first discovered does not preserve the required order.
• Use the original graph in the second pass.
• Reset the visited array between the two passes.
• The queue stores vertices in increasing finishing-time order; this is the key difference from the usual stack-based presentation.
• Like recursive DFS implementations generally, this code can hit the call-stack limit on very deep graphs. For extremely large constraints, consider iterative DFS.

Summary

The standard presentation processes vertices in decreasing finishing-time order on the transposed graph. This variation processes them in increasing finishing-time order on the original graph. Both identify SCCs in O(V + E) time.

Special Thanks to kazama460 for video editorial on kosaraju's Algortihm on his Youtube channel codeNcode.