Kosarajus SCC Algorithm: Algorithm Analysis and Code

1. Introduction and Core Concepts

Kosaraju's SCC algorithm, often referred to as the Kosaraju-Sharir algorithm, is a classic linear-time algorithm for finding all strongly connected components (SCCs) in a directed graph. A strongly connected component is a maximal subset of vertices where every vertex is reachable from every other vertex within the subset. Understanding SCCs is fundamental to analyzing the structure of directed graphs, which model everything from the World Wide Web to dependency networks and social interactions.

The importance of the kosarajus scc algorithm lies in its elegance, simplicity, and efficiency. Proposed independently by S. Rao Kosaraju and Micha Sharir in the late 1970s and popularized by Alfred Aho, John Hopcroft, and Jeffrey Ullman, the algorithm provides a clear two-pass depth-first search (DFS) strategy that is both easy to implement and easy to reason about. Unlike more complex single-pass algorithms, Kosaraju's approach leverages the concept of graph transposition and finishing times to systematically isolate SCCs, making it a staple in undergraduate algorithms courses and a reliable tool in production systems.

At its core, the algorithm answers a deceptively simple question: given a directed graph, how can we partition it into groups where mutual reachability holds? This decomposition reveals the condensation of the graph — a directed acyclic graph (DAG) where each node represents an SCC. This DAG structure is immensely powerful because many problems that are hard on general directed graphs become tractable on DAGs. For instance, finding cycles, determining reachability, or performing topological ordering can be simplified once SCCs are contracted.

What is a Strongly Connected Component?

Formally, for a directed graph G = (V, E), a strongly connected component is a maximal set C ⊆ V such that for every pair of vertices u, v ∈ C, there exists a directed path from u to v and a directed path from v to u. Maximal means that no additional vertex from V can be added to C without breaking this property. Every vertex belongs to exactly one SCC, so the SCCs partition the vertex set V.

Consider a graph representing web pages as vertices and hyperlinks as directed edges. An SCC in this graph represents a cluster of pages where you can navigate from any page in the cluster to any other page by following links. Identifying these clusters is crucial for search engines, web crawling strategies, and community detection. The kosarajus scc algorithm provides an efficient way to discover this hidden structure.

Why Kosaraju's Algorithm Matters

The kosarajus scc algorithm is significant for three primary reasons: conceptual clarity, linear time complexity, and practical utility. Its two-pass DFS structure is intuitive and serves as an excellent introduction to more advanced graph algorithms. It runs in O(V + E) time, which is asymptotically optimal since any algorithm must examine all vertices and edges. Furthermore, its implementation requires only standard DFS and graph reversal, both of which are well-understood primitives available in any graph library.

2. How It Works

Kosaraju's algorithm operates on two key insights from depth-first search. The first insight relates to the finishing times of DFS. When we perform a DFS on a directed graph, vertices that belong to a "sink" SCC — an SCC with no outgoing edges to other SCCs — will tend to finish last in a way that can be exploited. More precisely, if we consider the condensation DAG of SCCs, the SCC that finishes last in a DFS (i.e., has the vertex with the highest finishing time) must be a source SCC in the original graph.

The second insight is that reversing the direction of all edges (creating the transpose graph G^T) reverses the structure of the condensation DAG. A source SCC in G becomes a sink SCC in G^T, and vice versa. By combining these two ideas, the algorithm can iteratively peel off SCCs one by one. If we process vertices in decreasing order of their finishing times from the first DFS and then run DFS on the transpose graph, each DFS tree discovered in the second pass will correspond to exactly one SCC.

This elegant interplay between finishing times and graph transposition is what makes the kosarajus scc algorithm work. The first pass is purely for ordering; it does not identify components. The second pass, guided by that ordering, does the actual extraction of components in the reversed graph.

The Two-Pass Mechanism

Pass 1: Order by Finishing Time. Perform a DFS on the original graph G. As each vertex finishes (i.e., all its descendants have been explored), push it onto a stack. At the end of this pass, the stack contains vertices ordered by decreasing finishing time — the vertex that finished last is on top.

Transpose the Graph. Construct G^T, the transpose of G, by reversing every edge. If G contains an edge u → v, then G^T contains an edge v → u. This can be done in O(V + E) time by iterating through the adjacency list.

Pass 2: Discover SCCs in Reverse Order. Pop vertices one by one from the stack. For each unvisited vertex v popped, perform a DFS/BFS on G^T starting from v. All vertices reachable in this DFS form one strongly connected component. Mark them as visited and assign them a component ID. Continue until the stack is empty.

Intuition Behind Correctness

Why does processing in decreasing finishing time on the transpose guarantee correct SCCs? Consider two SCCs, C1 and C2, where there is an edge from C1 to C2 in G. During the first DFS, the DFS will finish all vertices in C2 before finishing vertices in C1 if it starts in C1 and reaches C2, or it will finish them in an order that ensures the representative of C1 appears after C2 on the stack. In either case, C1's representative will be higher on the stack than C2's. In G^T, the edge direction is reversed (C2 → C1), so starting a DFS from C1 in G^T cannot reach C2. Therefore, the DFS from C1 will be confined to C1 itself. This property holds inductively, ensuring each second-pass DFS is trapped within a single SCC.

3. Implementation

Implementing the kosarajus scc algorithm in Python is straightforward using adjacency lists and iterative or recursive DFS. Below are several implementation variants that demonstrate clarity, robustness, and scalability. All implementations assume the graph is represented as an adjacency list where graph[u] contains a list of neighbors v such that edge u → v exists.

Classic Recursive Implementation

This is the most readable version and is ideal for interviews and educational purposes. It uses recursion for both DFS passes and explicitly builds the transpose graph.

def kosaraju_recursive(n, graph):
    """
    Find SCCs using Kosaraju's algorithm (recursive).
    n: number of vertices (0 to n-1)
    graph: adjacency list for original graph G
    Returns: list of SCCs, each SCC is a list of vertices
    """
    visited = [False] * n
    stack = []  # stores vertices by finishing time

    # --- First Pass: DFS on G to compute finishing order ---
    def dfs_first(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs_first(v)
        stack.append(u)  # push after exploring descendants

    for u in range(n):
        if not visited[u]:
            dfs_first(u)

    # --- Build Transpose Graph G^T ---
    transpose = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            transpose[v].append(u)  # reverse edge u -> v to v -> u

    # --- Second Pass: DFS on G^T in reverse finishing order ---
    visited = [False] * n
    sccs = []

    def dfs_second(u, component):
        visited[u] = True
        component.append(u)
        for v in transpose[u]:
            if not visited[v]:
                dfs_second(v, component)

    while stack:
        u = stack.pop()
        if not visited[u]:
            comp = []
            dfs_second(u, comp)
            sccs.append(comp)

    return sccs

Iterative Implementation to Avoid Recursion Limits

Python has a default recursion limit (typically 1000), which can be exceeded on large or deep graphs (e.g., a path graph with 10,000 nodes). An iterative DFS using an explicit stack avoids RecursionError and is preferred for production code.

def kosaraju_iterative(n, graph):
    """
    Iterative Kosaraju to handle large graphs without recursion.
    Uses explicit stack for finishing time computation.
    """
    visited = [False] * n
    order = []

    # First pass: iterative DFS to compute post-order
    for start in range(n):
        if visited[start]:
            continue
        stack = [(start, 0)]  # (node, next_neighbor_index)
        visited[start] = True
        while stack:
            u, idx = stack[-1]
            if idx < len(graph[u]):
                v = graph[u][idx]
                stack[-1] = (u, idx + 1)
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, 0))
            else:
                order.append(u)
                stack.pop()

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

    # Second pass: iterative DFS on transpose
    visited = [False] * n
    sccs = []
    for u in reversed(order):
        if not visited[u]:
            comp = []
            stack = [u]
            visited[u] = True
            while stack:
                cur = stack.pop()
                comp.append(cur)
                for w in transpose[cur]:
                    if not visited[w]:
                        visited[w] = True
                        stack.append(w)
            sccs.append(comp)
    return sccs

Building Graph and Transpose Efficiently

In many applications, edges are provided as a list of pairs. This helper demonstrates clean construction and also returns a component ID mapping, which is often more useful than a list of lists for downstream processing like building the condensation DAG.

def build_graph(n, edge_list):
    """Build adjacency list from edge list."""
    g = [[] for _ in range(n)]
    gt = [[] for _ in range(n)]
    for u, v in edge_list:
        if 0 <= u < n and 0 <= v < n:
            g[u].append(v)
            gt[v].append(u)  # build transpose simultaneously
    return g, gt

def kosaraju_with_ids(n, graph, transpose):
    """
    Returns comp_id array where comp_id[v] is the SCC id of v,
    and total number of components.
    """
    visited = [False] * n
    order = []

    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

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

    comp_id = [-1] * n
    current_id = 0
    visited = [False] * n

    def dfs2(u, cid):
        visited[u] = True
        comp_id[u] = cid
        for v in transpose[u]:
            if not visited[v]:
                dfs2(v, cid)

    for u in reversed(order):
        if not visited[u]:
            dfs2(u, current_id)
            current_id += 1

    return comp_id, current_id

Complete Example with Condensation DAG

Often after finding SCCs, we want to build the condensation graph — the DAG of SCCs. This is useful for topological sorting of components or for dynamic programming on the DAG.

def condensation_dag(n, graph, comp_id, num_comps):
    """
    Build condensation DAG from SCC assignment.
    Returns adjacency list of DAG (as set to avoid duplicate edges).
    """
    dag = [set() for _ in range(num_comps)]
    indegree = [0] * num_comps
    for u in range(n):
        cu = comp_id[u]
        for v in graph[u]:
            cv = comp_id[v]
            if cu != cv and cv not in dag[cu]:
                dag[cu].add(cv)
                indegree[cv] += 1
    # Convert sets to lists for easier use
    dag = [list(s) for s in dag]
    return dag, indegree

# Example usage
if __name__ == "__main__":
    n = 8
    edges = [(0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3),(6,5),(6,7),(7,6)]
    g, gt = build_graph(n, edges)
    comp_id, k = kosaraju_with_ids(n, g, gt)
    print(f"Number of SCCs: {k}")
    print(f"Component IDs: {comp_id}")
    dag, indeg = condensation_dag(n, g, comp_id, k)
    print(f"Condensation DAG: {dag}")

4. Step-by-Step Example

To solidify understanding, let's walk through the kosarajus scc algorithm on a concrete directed graph with 8 vertices. This example is chosen to contain multiple SCCs of varying sizes, including a singleton, to illustrate all cases.

Consider graph G with vertices {0,1,2,3,4,5,6,7} and edges: 0→1, 1→2, 2→0 (forming SCC A = {0,1,2}), 2→3, 3→4, 4→5, 5→3 (forming SCC B = {3,4,5}), 6→5, 6→7, 7→6 (forming SCC C = {6,7}). Note that there is an edge from A to B (2→3) and from C to B (6→5), but no edges back. The condensation DAG is A → B ← C.

Pass 1: DFS on Original Graph G

We perform DFS starting from vertex 0 (assuming numerical order for unvisited vertices). The traversal might proceed as: start at 0 → 1 → 2 → 0 (already visited) → 3 → 4 → 5 → 3 (already visited). At this point, 5 finishes and is pushed to stack, then 4, then 3. Backtrack to 2, then 1, then 0 — they finish and are pushed. Stack currently (bottom to top): [5,4,3,2,1,0]. Next, start DFS from 6 (the next unvisited): 6 → 5 (visited) → 7 → 6 (visited). 7 finishes and is pushed, then 6 finishes and is pushed. Final stack (bottom to top): [5,4,3,2,1,0,7,6]. Therefore, order of decreasing finishing time (top to bottom) is: 6, 7, 0, 1, 2, 3, 4, 5.

The exact order may vary slightly depending on adjacency list ordering, but the crucial property holds: representatives of source SCCs (A and C) appear before the sink SCC (B). In this case, 6 (from C) and 0 (from A) are at the top, while vertices from B are at the bottom.

Transpose Graph G^T

We reverse every edge: 1→0, 2→1, 0→2, 3→2, 4→3, 5→4, 3→5, 5→6, 7→6, 6→7. Notice that SCCs remain the same, but edges between them are reversed: B → A and B → C in G^T.

Pass 2: DFS on Transpose Graph G^T in Stack Order

We pop from the stack and run DFS on G^T:

1. Pop 6: DFS on G^T from 6 visits 6 → 7 → 6 (cycle). No edge leads to B or A in G^T from C? Actually G^T has no edge from C to B, only B to C is reversed? Wait G had 6→5, so G^T has 5→6, not 6→5. So starting at 6, we only reach {6,7}. First SCC found: {6,7} = C. Mark visited.
2. Pop 7: Already visited, skip.
3. Pop 0: DFS on G^T from 0 visits 0 → 2 → 1 → 0 (cycle). It cannot reach B because G^T has edge 3→2, not 2→3. So second SCC: {0,1,2} = A. Mark visited.
4. Pop 1, 2: Already visited, skip.
5. Pop 3: DFS on G^T from 3 visits 3 → 5 → 4 → 3 (cycle). Third SCC: {3,4,5} = B. Mark visited.
6. Pop 4, 5: Already visited, skip.

Result: Three SCCs correctly identified as {6,7}, {0,1,2}, and {3,4,5}. The order in which they were discovered is reverse topological order of the condensation DAG in G, which is topological order in G^T. This walkthrough demonstrates how the finishing time ordering isolates sink components first in the transpose graph.

5. Complexity Analysis

The kosarajus scc algorithm is asymptotically optimal for finding strongly connected components. Its efficiency comes from the fact that each vertex and edge is processed a constant number of times. Understanding its complexity in best, average, and worst cases is essential for system design, especially when dealing with large-scale graphs such as social networks with billions of edges.

The algorithm consists of three distinct phases, each with linear cost: the first DFS, the graph transposition, and the second DFS. Because these phases are sequential and each is O(V + E), the overall complexity remains linear. Unlike algorithms with superlinear worst-case behavior, Kosaraju's performance degrades gracefully and predictably as the graph grows.

Time and Space Breakdown

In the best case (e.g., a graph with no edges or a highly disconnected graph), the DFS still must visit every vertex, so the time is still proportional to V. In the worst case (a dense graph where E approaches V²), the time is dominated by edge traversal. Space complexity is dominated by storing the graph, its transpose, and auxiliary arrays (visited, stack, component IDs).

Detailed Analysis

Time Complexity: The first DFS visits each vertex once and traverses each adjacency list once, costing O(V + E). Building the transpose iterates over all edges once, also O(V + E). The second DFS again visits each vertex and edge in the transpose graph exactly once, O(V + E). Summing these, total time is O(V + E). This holds for all cases — best, average, and worst — because the algorithm has no early exit or data-dependent branching that changes asymptotic behavior. Even for an empty graph (E=0), it still does O(V) work to initialize and scan vertices.

Space Complexity: We store the original graph O(V + E), the transpose graph O(V + E), the visited boolean array O(V), the finishing order stack O(V), and the component ID array O(V). Total auxiliary space is O(V + E). The recursion stack in the recursive version can grow to O(V) in the worst case (a long path), which may cause stack overflow in languages like Python. The iterative version replaces recursion stack with an explicit heap-allocated stack, still O(V) but without interpreter limits.

Comparison to Lower Bound: Any algorithm that finds SCCs must at least read the entire graph, which is Ω(V + E). Since Kosaraju achieves O(V + E), it is asymptotically optimal. No algorithm can do better in Big O terms.

6. Variations and Optimizations

While the classic kosarajus scc algorithm is already optimal asymptotically, several variations and optimizations improve its practical performance, memory footprint, and applicability to specific constraints such as streaming graphs or external memory.

Iterative and Hybrid DFS

As shown in the implementation section, replacing recursion with an explicit stack avoids Python's recursion limit and can improve cache locality. A further optimization is to use iterative DFS only for the first pass (where depth can be large) and recursion for the second pass (where SCCs may be smaller), or vice versa. Some implementations use a single array for both visited states and finishing order to reduce memory passes.

Single Transpose Optimization

Instead of explicitly building the full transpose graph as a separate adjacency list (which doubles memory), we can build it on the fly if edges are stored in an edge list. Alternatively, if the graph is stored as an adjacency list of sets, we can build the transpose in place by iterating once. For very large graphs that do not fit in RAM, the transpose can be generated externally by sorting edges by destination vertex, or by storing both forward and reverse adjacency lists during initial graph construction to avoid a second pass.

Early Exit and Pruning

If only the SCC containing a specific vertex is needed, we can optimize by running a forward DFS from that vertex and a backward DFS on the transpose from the same vertex; their intersection is the SCC. This is O(V + E) worst-case but often much faster in practice. For counting SCCs without enumerating them, we can avoid storing full component lists and just count.

Parallel and Distributed Variants

For massive graphs (e.g., web graphs with billions of nodes), parallel Kosaraju can be implemented using parallel DFS or BFS. However, DFS is inherently sequential, so alternative parallel SCC algorithms like Forward-Backward (FWD-BWD) or coloring-based algorithms are often preferred. A common optimization is to use Kosaraju for medium-sized graphs and switch to iterative bit-parallel methods for huge graphs.

Memory Optimization: In-Place Stack

We can reuse the same visited array for both passes by resetting it, and we can store finishing order in a simple Python list of integers. Using arrays from the `array` module or `list` of `int` is more memory-efficient than using objects. For sparse graphs, using `defaultdict(list)` may save space compared to a full list of size V if vertices are not densely numbered.

7. Real-World Applications

Strongly connected components are not just a theoretical curiosity; they underpin critical functionality in web infrastructure, databases, networking, and software engineering. The kosarajus scc algorithm, due to its simplicity and reliability, is frequently the first choice for these tasks when graph sizes are moderate and implementation clarity is valued.

Any system that can be modeled as a directed graph where mutual reachability matters can benefit from SCC analysis. The condensation DAG derived from SCCs often reveals hierarchical structure, bottlenecks, and cyclic dependencies that are invisible in the raw graph.

Detailed Use Cases

Web Servers and Crawlers: Search engines like Google use SCC analysis to understand the web's bow-tie structure. The largest SCC (often called the core) contains pages that are mutually reachable. Kosaraju helps identify this core and the IN and OUT components, optimizing crawl budget by prioritizing the core and detecting spider traps — SCCs with many internal links but few outgoing links that can trap a crawler.

Databases: In a relational database's wait-for graph, an edge T1 → T2 means transaction T1 waits for a lock held by T2. A cycle in this graph indicates deadlock. Since any cycle is contained within an SCC, finding SCCs with more than one node (or a self-loop) immediately identifies deadlocked transactions. Database deadlock detectors run SCC algorithms periodically with very low latency requirements, where Kosaraju's linear time is critical.

Software Engineering: Package managers (npm, pip, Maven) build a dependency graph. An SCC with more than one package indicates a circular dependency, which complicates installation and versioning. Tools run SCC detection to warn developers and to compute a valid installation order by topologically sorting the condensation DAG. Kosaraju's simple implementation makes it easy to embed in build tools.

8. Comparison with Alternatives

Kosaraju's algorithm is one of three major linear-time SCC algorithms, alongside Tarjan's algorithm and Gabow's (or Cheriyan-Mehlhorn-Gabow) algorithm. While all achieve O(V + E) time, they differ significantly in implementation complexity, number of passes, memory usage, and practical constants. Choosing the right algorithm depends on constraints such as recursion depth, memory limits, and need for online processing.

Brute-force approaches, such as running BFS/DFS from every vertex to check mutual reachability (O(V*(V+E))), are only feasible for tiny graphs and serve as a baseline to appreciate the linear algorithms. The table below provides a comprehensive feature comparison.

When to Choose Kosaraju

Choose the kosarajus scc algorithm when code clarity and correctness are paramount, such as in interviews, educational settings, or when you need a quickly verifiable implementation. Its two-pass structure is less error-prone than Tarjan's lowlink updates, which are a common source of bugs (e.g., incorrectly updating lowlink on cross edges vs. back edges). Kosaraju is also easier to parallelize in its second phase because each DFS on the transpose is independent once the order is known.

Choose Tarjan or Gabow when memory is tight (you cannot afford to store the transpose) or when you need the absolute best constant factors for huge graphs. Tarjan's algorithm is generally considered the most efficient in practice due to its single pass, but it is harder to implement iteratively without recursion.

For brute force, never use it beyond n < 100. For example, a brute-force SCC check that runs Floyd-Warshall (O(V³)) or repeated BFS will be orders of magnitude slower than Kosaraju on a graph with 10,000 nodes.

9. Common Mistakes and Best Practices

Despite its conceptual simplicity, implementing the kosarajus scc algorithm correctly requires attention to several subtle pitfalls. Many bugs stem from mishandling the transpose, visited state, or recursion limits, leading to incorrect components or runtime errors on large inputs.

Frequent Pitfalls

Forgetting to Reset Visited: The most common mistake is reusing the same visited array for both passes without resetting it. After the first DFS, all vertices are marked visited. If you do not clear or create a new visited array before the second pass, the second DFS will do nothing and return zero components. Always reinitialize visited = [False]*n between passes.

Incorrect Transpose Construction: Reversing edges incorrectly — for example, adding edges to the original graph instead of the transpose, or missing edges due to off-by-one errors — will produce wrong SCCs. Verify that for every edge u → v in G, you add v → u in G^T and that you iterate over all vertices, including isolated ones.

Processing Order in Second Pass: The second pass must process vertices in decreasing finishing time, i.e., popping from the stack (LIFO). Processing in increasing order (queue) or in arbitrary order breaks correctness. Ensure you use stack.pop() and not stack.pop(0) or iterating in forward order. Also, ensure the first pass pushes vertices in post-order (after exploring neighbors), not pre-order.

Recursion Limit and Stack Overflow: In Python, a deep DFS on a path graph with 2000 vertices will exceed the default recursion limit of 1000 and raise RecursionError. Use sys.setrecursionlimit(10000) as a temporary fix, but prefer the iterative implementation for robustness. In other languages like Java or C++, stack overflow can still occur with recursion on large graphs.

Handling Self-Loops and Isolated Vertices: A vertex with a self-loop (v → v) forms an SCC of size 1 that is considered strongly connected (trivially). An isolated vertex with no edges also forms an SCC of size 1. Ensure your algorithm correctly reports these as separate components rather than merging them or ignoring them. The loop for i in range(n): if not visited[i]: dfs(i) ensures isolated vertices are processed.

Best Practices

• Use Iterative DFS for Production: Always provide an iterative fallback for large graphs. Test with a long chain graph (0→1→2→...→n-1) to verify you handle depth.
• Validate with Small Cases: Test on known graphs: empty graph (n=0), single node, two nodes with one directed edge (two SCCs), two nodes with two edges (one SCC), and the example from Section 4.
• Use Component IDs Instead of Lists: For downstream tasks like building the condensation DAG, returning an array comp_id where comp_id[v] = component number is more efficient than returning list-of-lists. It allows O(1) lookup of a vertex's component.
• Escape and Sanitize Input: If reading graph data from files or user input, validate that vertex indices are within [0, n-1] and handle duplicate edges gracefully (they do not affect correctness but may waste time).
• Document Complexity: Clearly comment that the algorithm is O(V + E) time and O(V + E) space, and note the trade-off of extra memory for the transpose versus Tarjan's single-pass memory savings.

10. Interview Questions

Mastering the kosarajus scc algorithm is a strong signal in technical interviews for roles involving graphs, backend systems, or data engineering. Interviewers often use SCC problems to test understanding of DFS, graph reversal, and DAG condensation. Below are common questions with guidance on how to approach them.

Q1: Explain Kosaraju's Algorithm and Why the Second Pass Must Be on the Transpose Graph

What interviewers look for: A clear explanation of finishing times, the source-sink reversal property, and why processing in decreasing finishing time on G^T isolates SCCs. A strong answer will walk through the intuition: the vertex with highest finishing time belongs to a source SCC in G, which becomes a sink in G^T, so its DFS in G^T cannot leave the SCC.

Sample answer outline: Describe the three steps (DFS order, transpose, DFS in reverse order), prove correctness by contradiction using the condensation DAG, and state O(V+E) complexity. Mention that without transposition, a DFS from a source SCC would spill over into downstream SCCs and merge them incorrectly.

Q2: How Would You Find the Number of SCCs and the Size of the Largest SCC?

Approach: Run Kosaraju to get comp_id and num_comps. Count frequencies of each comp_id using a dictionary or Counter. Number of SCCs is num_comps; largest size is max(freq.values()). Complexity remains O(V+E). Be prepared to code this live, handling edge cases like empty graph. Discuss iterative vs. recursive implementation trade-offs if asked about large graphs.

Q3: Given a Directed Graph, Determine If It Is Strongly Connected (Single SCC)

Approach: A graph is strongly connected iff Kosaraju returns exactly one SCC. Optimization: you can early exit — run first DFS from arbitrary node 0; if not all nodes visited, not strongly connected. Then run DFS on transpose from same node; if not all visited, not strongly connected. This is essentially Kosaraju with early termination and uses only two DFS traversals without full ordering, O(V+E). Explain why this works: strong connectivity requires reachability both ways from any node.

Q4: How Do You Find All Vertices That Are Part of a Cycle?

Approach: A vertex is part of a directed cycle iff it belongs to an SCC with size > 1 or has a self-loop. So find SCCs via Kosaraju, then collect all vertices where len(scc) > 1 or graph[v] contains v. This is a classic reduction from cycle detection to SCC. Discuss alternative: Tarjan would also work, but Kosaraju is simpler to explain. Mention that condensation DAG is acyclic, so any cycle must be inside an SCC.

Q5: Compare Kosaraju and Tarjan — When Would You Prefer One Over the Other?

Approach: Provide the comparison table from Section 8. Emphasize that both are O(V+E) but Kosaraju uses two passes and extra memory for transpose, making it easier to implement and debug, ideal for interviews. Tarjan uses one pass and O(V) extra memory, better for memory-constrained production or huge graphs. Mention that Kosaraju's second pass is embarrassingly parallelizable, while Tarjan's is inherently sequential due to lowlink dependencies. Conclude with a recommendation based on context.

Preparing concise, correct code for the kosarajus scc algorithm and being able to reason about its correctness and trade-offs will set you apart in graph algorithm interviews. Practice writing both recursive and iterative versions from memory, and be ready to adapt the core idea to related problems like 2-SAT, which relies heavily on SCC decomposition.