Tarjan's Strongly Connected Components

Generated on 2025-07-10 01:59:48 Algorithm Cheatsheet for Technical Interviews

---

Tarjan’s Strongly Connected Components (SCC) Cheatsheet

1. Quick Overview

Tarjan’s algorithm finds all strongly connected components (SCCs) in a directed graph. A strongly connected component is a maximal set of vertices such that for every pair of vertices u and v in the set, there is a path from u to v and a path from v to u.

When to Use:

• Finding SCCs in a directed graph.
• Condensing a directed graph into a directed acyclic graph (DAG) by treating each SCC as a single node.
• Solving problems involving cycle detection and dependence analysis.

2. Time & Space Complexity

Operation	Complexity	Explanation
Time Complexity	O(V + E)	Where V is the number of vertices and E is the number of edges. The algorithm visits each vertex and edge at most once.
Space Complexity	O(V)	Primarily due to the recursion stack, ids, low, and onStack arrays. In the worst case, all vertices could be in the stack simultaneously.

3. Implementation

Python

def tarjan_scc(graph):
    """
    Finds strongly connected components (SCCs) in a directed graph using Tarjan's algorithm.

    Args:
        graph: A dictionary representing the graph, where keys are vertices and values are lists of their neighbors.

    Returns:
        A list of lists, where each inner list represents a strongly connected component.
    """
    index = 0
    stack = []
    on_stack = {}  # Keep track of nodes currently on the stack
    ids = {}      # Assign unique id to each node
    low = {}      # Lowest reachable node from each node
    sccs = []     # Store the SCCs

    def dfs(node):
        nonlocal index
        ids[node] = index
        low[node] = index
        index += 1
        stack.append(node)
        on_stack[node] = True

        for neighbor in graph.get(node, []):
            if neighbor not in ids: # Not visited
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])
            elif on_stack.get(neighbor, False): # Visited and on stack
                low[node] = min(low[node], ids[neighbor])

        if low[node] == ids[node]:
            scc = []
            while True:
                popped_node = stack.pop()
                on_stack[popped_node] = False
                scc.append(popped_node)
                if popped_node == node:
                    break
            sccs.append(scc)

    for node in graph:
        if node not in ids:
            dfs(node)

    return sccs

# Example usage:
graph = {
    0: [1],
    1: [2, 3],
    2: [0],
    3: [4],
    4: [5],
    5: [3, 6],
    6: [7],
    7: [8],
    8: [6]
}

sccs = tarjan_scc(graph)
print("Strongly Connected Components:", sccs)

Java

import java.util.*;

public class TarjanSCC {

    private int index;
    private Stack<Integer> stack;
    private boolean[] onStack;
    private int[] ids;
    private int[] low;
    private List<List<Integer>> sccs;
    private Map<Integer, List<Integer>> graph;
    private int n; // number of nodes

    public TarjanSCC(Map<Integer, List<Integer>> graph, int n) {
        this.graph = graph;
        this.n = n;
        index = 0;
        stack = new Stack<>();
        onStack = new boolean[n];
        ids = new int[n];
        low = new int[n];
        sccs = new ArrayList<>();
        Arrays.fill(ids, -1); // Mark all nodes as unvisited
    }

    public List<List<Integer>> findSCCs() {
        for (int i = 0; i < n; i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccs;
    }

    private void dfs(int node) {
        ids[node] = index;
        low[node] = index;
        index++;
        stack.push(node);
        onStack[node] = true;

        if (graph.containsKey(node)) {
            for (int neighbor : graph.get(node)) {
                if (ids[neighbor] == -1) {
                    dfs(neighbor);
                    low[node] = Math.min(low[node], low[neighbor]);
                } else if (onStack[neighbor]) {
                    low[node] = Math.min(low[node], ids[neighbor]);
                }
            }
        }


        if (low[node] == ids[node]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int poppedNode = stack.pop();
                onStack[poppedNode] = false;
                scc.add(poppedNode);
                if (poppedNode == node) {
                    break;
                }
            }
            sccs.add(scc);
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1));
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(0));
        graph.put(3, Arrays.asList(4));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(3, 6));
        graph.put(6, Arrays.asList(7));
        graph.put(7, Arrays.asList(8));
        graph.put(8, Arrays.asList(6));

        TarjanSCC tarjanSCC = new TarjanSCC(graph, 9); // Assuming 9 nodes
        List<List<Integer>> sccs = tarjanSCC.findSCCs();

        System.out.println("Strongly Connected Components: " + sccs);
    }
}

C++

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

using namespace std;

class TarjanSCC {
public:
    TarjanSCC(const vector<vector<int>>& adj) : adj(adj), n(adj.size()), index(0) {
        ids.resize(n, -1); // Initialize with -1 to indicate unvisited
        low.resize(n);
        onStack.resize(n, false);
    }

    vector<vector<int>> findSCCs() {
        for (int i = 0; i < n; ++i) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccs;
    }

private:
    void dfs(int u) {
        ids[u] = low[u] = index++;
        stack_.push(u);
        onStack[u] = true;

        for (int v : adj[u]) {
            if (ids[v] == -1) { // Not visited
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (onStack[v]) { // Visited and on stack
                low[u] = min(low[u], ids[v]);
            }
        }

        if (low[u] == ids[u]) {
            vector<int> scc;
            while (true) {
                int v = stack_.top();
                stack_.pop();
                onStack[v] = false;
                scc.push_back(v);
                if (v == u) break;
            }
            sccs.push_back(scc);
        }
    }

private:
    const vector<vector<int>>& adj;
    int n;
    int index;
    stack<int> stack_;
    vector<int> ids;
    vector<int> low;
    vector<bool> onStack;
    vector<vector<int>> sccs;
};

int main() {
    vector<vector<int>> adj = {
        {1},       // 0
        {2, 3},    // 1
        {0},       // 2
        {4},       // 3
        {5},       // 4
        {3, 6},    // 5
        {7},       // 6
        {8},       // 7
        {6}        // 8
    };

    TarjanSCC tarjan(adj);
    vector<vector<int>> sccs = tarjan.findSCCs();

    cout << "Strongly Connected Components:" << endl;
    for (const auto& scc : sccs) {
        cout << "[";
        for (int v : scc) {
            cout << v << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

4. Common Patterns

• Condensation Graph: Create a new graph where each SCC is represented by a single node. Edges connect SCCs if there’s an edge between vertices in those SCCs in the original graph. This results in a DAG.
• Cycle Detection: If Tarjan’s algorithm finds more than one SCC, the graph contains at least one cycle.
• Topological Sort of SCCs: After finding SCCs, you can perform a topological sort on the condensation graph.
• Path finding within SCCs: Often, after identifying SCCs, you need to solve another problem, but only within each SCC.

5. Pro Tips

• Initialization: Make sure to initialize ids, low, and onStack correctly. The ids array should typically be initialized with a value that indicates that the node has not been visited yet (e.g., -1). onStack should be initialized with false for all nodes.
• Stack Management: Ensure proper stack management. A common mistake is not pushing nodes onto the stack or not popping them off when they belong to an SCC.
• Understanding low values: The low value represents the lowest node ID reachable from a given node. It’s crucial for determining the “root” of an SCC.
• Graph Representation: Choose the appropriate graph representation (adjacency list or adjacency matrix) based on the graph’s density. Adjacency lists are generally more efficient for sparse graphs.
• Non-existent Edges: Handle cases where a node might not have any outgoing edges. This is especially important when using dictionary-based graph representations. Use graph.get(node, []) to safely handle missing nodes.

6. Practice Problems

1. LeetCode 1192. Critical Connections in a Network: While not directly an SCC problem, the concept of finding low-link values is very similar to Tarjan’s algorithm. You need to find bridges (edges whose removal disconnects the graph).

   # LeetCode 1192 (Conceptual Outline)
   def criticalConnections(n, connections):
       graph = [[] for _ in range(n)]
       for u, v in connections:
           graph[u].append(v)
           graph[v].append(u)
   
       low = [0] * n
       ids = [0] * n
       parent = [-1] * n
       timer = 0
       result = []
   
       def dfs(node):
           nonlocal timer
           ids[node] = low[node] = timer
           timer += 1
   
           for neighbor in graph[node]:
               if neighbor == parent[node]:
                   continue
               if ids[neighbor] == 0:
                   parent[neighbor] = node
                   dfs(neighbor)
                   low[node] = min(low[node], low[neighbor])
                   if low[neighbor] > ids[node]:
                       result.append([node, neighbor])
               else:
                   low[node] = min(low[node], ids[neighbor])
   
       dfs(0)
       return result

2. LeetCode 207. Course Schedule: Check if a course schedule is possible given prerequisites. This can be modeled as a directed graph, and cycles indicate that the schedule is impossible. You can use Tarjan’s to detect cycles (if SCC count > 1, then cycle exists)

   # LeetCode 207 (Conceptual Outline)
   def canFinish(numCourses, prerequisites):
       graph = [[] for _ in range(numCourses)]
       for course, pre in prerequisites:
           graph[pre].append(course)
   
       # Apply Tarjan's or a simpler cycle detection using DFS
       # If a cycle is found, return False
       # Otherwise, return True
       # (Full implementation using Tarjan's would be similar to the example above)
       # Instead, you might use DFS with a 'visiting' set to detect cycles more directly.
       return True # Placeholder

3. Codeforces 118E - Bertown Roads: Given an undirected graph, orient its edges so that the resulting directed graph is strongly connected. If there is no such orientation, output 0.

   // Codeforces 118E - Bertown Roads (Conceptual Outline)
   // Requires adaptation of Tarjan's to handle undirected graph and edge orientation
   // The key idea is to find bridges and if there are any, no solution exists.
   // Otherwise, orient the edges based on DFS traversal direction.

7. Templates

C++

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

using namespace std;

class TarjanSCC {
public:
    TarjanSCC(const vector<vector<int>>& adj) : adj(adj), n(adj.size()), index(0) {
        ids.resize(n, -1);
        low.resize(n);
        onStack.resize(n, false);
    }

    vector<vector<int>> findSCCs() {
        for (int i = 0; i < n; ++i) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccs;
    }

private:
    void dfs(int u) {
        ids[u] = low[u] = index++;
        stack_.push(u);
        onStack[u] = true;

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

        if (low[u] == ids[u]) {
            vector<int> scc;
            while (true) {
                int v = stack_.top();
                stack_.pop();
                onStack[v] = false;
                scc.push_back(v);
                if (v == u) break;
            }
            sccs.push_back(scc);
        }
    }

private:
    const vector<vector<int>>& adj;
    int n;
    int index;
    stack<int> stack_;
    vector<int> ids;
    vector<int> low;
    vector<bool> onStack;
    vector<vector<int>> sccs;
};

Python

def tarjan_scc(graph):
    index = 0
    stack = []
    on_stack = {}
    ids = {}
    low = {}
    sccs = []

    def dfs(node):
        nonlocal index
        ids[node] = index
        low[node] = index
        index += 1
        stack.append(node)
        on_stack[node] = True

        for neighbor in graph.get(node, []):
            if neighbor not in ids:
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])
            elif on_stack.get(neighbor, False):
                low[node] = min(low[node], ids[neighbor])

        if low[node] == ids[node]:
            scc = []
            while True:
                popped_node = stack.pop()
                on_stack[popped_node] = False
                scc.append(popped_node)
                if popped_node == node:
                    break
            sccs.append(scc)

    for node in graph:
        if node not in ids:
            dfs(node)

    return sccs

Java

import java.util.*;

public class TarjanSCC {

    private int index;
    private Stack<Integer> stack;
    private boolean[] onStack;
    private int[] ids;
    private int[] low;
    private List<List<Integer>> sccs;
    private Map<Integer, List<Integer>> graph;
    private int n;

    public TarjanSCC(Map<Integer, List<Integer>> graph, int n) {
        this.graph = graph;
        this.n = n;
        index = 0;
        stack = new Stack<>();
        onStack = new boolean[n];
        ids = new int[n];
        low = new int[n];
        sccs = new ArrayList<>();
        Arrays.fill(ids, -1);
    }

    public List<List<Integer>> findSCCs() {
        for (int i = 0; i < n; i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccs;
    }

    private void dfs(int node) {
        ids[node] = index;
        low[node] = index;
        index++;
        stack.push(node);
        onStack[node] = true;

        if (graph.containsKey(node)) {
            for (int neighbor : graph.get(node)) {
                if (ids[neighbor] == -1) {
                    dfs(neighbor);
                    low[node] = Math.min(low[node], low[neighbor]);
                } else if (onStack[neighbor]) {
                    low[node] = Math.min(low[node], ids[neighbor]);
                }
            }
        }

        if (low[node] == ids[node]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int poppedNode = stack.pop();
                onStack[poppedNode] = false;
                scc.add(poppedNode);
                if (poppedNode == node) {
                    break;
                }
            }
            sccs.add(scc);
        }
    }
}