Skip to content

Tarjan's and Kosaraju's

Finding the Strongly Connected Pieces of a Directed Graph

In an undirected graph, connected components are trivial -- run DFS, mark visited nodes, done. Directed graphs are harder. Node A might reach node B, but B might not reach A. A strongly connected component (SCC) is a maximal set of nodes where every node can reach every other node. Finding these components requires smarter DFS tricks.

What Is an SCC?

A strongly connected component is a maximal subset of nodes in a directed graph such that for every pair (u, v) in the subset, there exists a path from u to v AND from v to u.

Every directed graph decomposes into SCCs. A single node with no self-loop is its own SCC. A cycle forms one SCC. The decomposition is unique.

Kosaraju's Algorithm

Kosaraju's two-pass DFS: first pass records finish order, second finds SCCs

Idea: Two passes of DFS. The first pass determines the "right order" to process nodes. The second pass, on the reversed graph, finds the SCCs.

Steps:

  1. Run DFS on the original graph. When a node finishes (all descendants explored), push it onto a stack.
  2. Reverse all edges in the graph.
  3. Pop nodes from the stack. For each unvisited node, run DFS on the reversed graph. All nodes reached form one SCC.
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN];
bool vis[MAXN];
vector<int> order;

void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs1(v);
    order.push_back(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    for (int v : radj[u])
        if (comp[v] == -1) dfs2(v, c);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);

    memset(comp, -1, sizeof(comp));
    int numSCC = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        if (comp[order[i]] == -1)
            dfs2(order[i], numSCC++);
    }

    cout << numSCC << "\n";
    for (int i = 1; i <= n; i++)
        cout << comp[i] + 1 << " \n"[i == n];
}

Complexity: O(V + E). Two DFS passes, each O(V + E).

💡 Key insight. Why does processing in reverse finish order work? The node that finishes last in pass 1 is in a "source" SCC (no incoming edges from other SCCs). DFS on the reversed graph from this node can only reach nodes in the same SCC, because incoming edges become outgoing and the source SCC has no outgoing edges in the reversed graph.

Tarjan's Algorithm

Tarjan's algorithm: SCCs identified by low-link values

Idea: Single DFS with discovery times and low-link values. A node is the root of an SCC if its low-link equals its discovery time.

Key variables: - disc[u] = when node u was first discovered - low[u] = the smallest discovery time reachable from u's subtree via back edges - A stack tracks the current DFS path

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

const int MAXN = 200005;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], comp[MAXN];
bool onStack[MAXN];
stack<int> st;
int timer_val = 0, numSCC = 0;

void tarjan(int u) {
    disc[u] = low[u] = timer_val++;
    st.push(u);
    onStack[u] = true;

    for (int v : adj[u]) {
        if (disc[v] == -1) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (onStack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }

    if (disc[u] == low[u]) {
        while (true) {
            int v = st.top(); st.pop();
            onStack[v] = false;
            comp[v] = numSCC;
            if (v == u) break;
        }
        numSCC++;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    memset(disc, -1, sizeof(disc));
    for (int i = 1; i <= n; i++)
        if (disc[i] == -1) tarjan(i);

    cout << numSCC << "\n";
    for (int i = 1; i <= n; i++)
        cout << comp[i] + 1 << " \n"[i == n];
}

⚠ Gotcha. In Tarjan's, only update low[u] from disc[v] (not low[v]) when v is already on the stack. If v is visited but not on the stack, it belongs to a finished SCC and should be ignored.

Full Trace: Kosaraju's on a 6-Node Graph

Graph edges: 1->2, 2->3, 3->1, 3->4, 4->5, 5->6, 6->4.

Pass 1 (DFS on original, record finish order):

Step Visit Action Stack (finish order)
1 1 Explore 1->2
2 2 Explore 2->3
3 3 Explore 3->1 (visited, skip)
4 3 Explore 3->4
5 4 Explore 4->5
6 5 Explore 5->6
7 6 Explore 6->4 (visited, skip)
8 6 Finish [6]
9 5 Finish [6, 5]
10 4 Finish [6, 5, 4]
11 3 Finish [6, 5, 4, 3]
12 2 Finish [6, 5, 4, 3, 2]
13 1 Finish [6, 5, 4, 3, 2, 1]

Pass 2 (DFS on reversed graph, process from top of stack):

Reversed edges: 2->1, 3->2, 1->3, 4->3, 5->4, 6->5, 4->6.

Pop Node DFS on reversed SCC
1 1 1->3->2 (all unvisited) {1, 2, 3}
2 2 Already visited --
3 3 Already visited --
4 4 4->6->5 (all unvisited) {4, 5, 6}
5 5 Already visited --
6 6 Already visited --

Result: Two SCCs: {1, 2, 3} and {4, 5, 6}.

CSES Planets and Kingdoms

Problem: N planets, M teleportation routes (directed). Assign each planet to a kingdom such that planets in the same kingdom can reach each other. Print the number of kingdoms and each planet's kingdom.

This is asking for SCCs directly.

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

const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN];
bool vis[MAXN];
vector<int> order;

void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs1(v);
    order.push_back(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    for (int v : radj[u])
        if (comp[v] == -1) dfs2(v, c);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);

    memset(comp, -1, sizeof(comp));
    int numSCC = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--)
        if (comp[order[i]] == -1)
            dfs2(order[i], numSCC++);

    cout << numSCC << "\n";
    for (int i = 1; i <= n; i++)
        cout << comp[i] + 1 << " \n"[i == n];
}

💡 Key insight. Kosaraju's gives you SCC IDs in reverse topological order of the condensation DAG. The first SCC found (comp = 0) is a source in the condensation. This ordering is free and useful for DP in later lessons.

Kosaraju's vs Tarjan's

Feature Kosaraju's Tarjan's
DFS passes 2 1
Extra storage Reversed graph Stack + low-link arrays
Complexity O(V + E) O(V + E)
SCC order Reverse topological Reverse topological
Easier to code? Yes (two simple DFS) Slightly trickier

In practice, Kosaraju's is easier to implement and debug. Tarjan's is faster by a constant factor (one DFS instead of two) but needs careful handling of the low-link updates.

Try It

The starter code has the DFS skeleton. Fill in dfs1 and dfs2.

Test case 1: 

Input:
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Output:
2
1 1 1 2 2 2

Test case 2: 

Input:
4 4
1 2
2 3
3 4
4 1

Output:
1
1 1 1 1

Problems

Problem Link Difficulty
CSES Planets and Kingdoms cses.fi/problemset/task/1683 Easy
practice2_g — SCC atcoder.jp/contests/practice2/tasks/practice2_g Easy