Tarjans Strongly Connected Components: Complete Implementation Guide

1. Introduction and Core Concepts

Tarjan's Strongly Connected Components (SCC) algorithm is one of the most elegant and efficient graph algorithms ever devised. Introduced by Robert Tarjan in 1972, it identifies all strongly connected components of a directed graph in a single depth-first search traversal. A strongly connected component is a maximal set of vertices such that every vertex is reachable from every other vertex in the set. Understanding this structure is fundamental to analyzing connectivity, dependency, and reachability in directed graphs.

In a directed graph, connectivity is not symmetric. While an undirected graph is either connected or not, a directed graph can have varying degrees of connectivity. Strong connectivity is the strongest form: for any two vertices u and v in an SCC, there exists a directed path from u to v and from v to u. Tarjan's algorithm partitions the entire vertex set into these equivalence classes, providing a complete decomposition of the graph's reachability structure. This decomposition is unique and forms the basis for many higher-level graph operations.

Why does this matter? Many real-world systems are modeled as directed graphs — the web, software dependencies, social networks, and transaction graphs. Identifying SCCs reveals tightly coupled clusters where circular dependencies or feedback loops exist. For example, a cycle in a package dependency graph means no valid installation order exists without breaking the cycle. By compressing each SCC into a single meta-node, we obtain the condensation graph, which is always a Directed Acyclic Graph (DAG). This DAG can then be topologically sorted, enabling efficient scheduling, reachability queries, and analysis that would be impossible on the original cyclic graph.

Key Definitions

To understand Tarjan's algorithm, you must be familiar with three core concepts. First, discovery time (or index): the order in which vertices are first visited during depth-first search (DFS). Second, low-link value: the smallest discovery time reachable from a vertex by traversing zero or more tree edges followed by at most one back edge. Third, DFS stack: the stack of vertices that have been visited but not yet assigned to an SCC. A vertex remains on the stack until its SCC is fully identified.

The brilliance of Tarjan's approach lies in how it combines these concepts. The low-link value allows the algorithm to detect when a vertex is the root of an SCC. If a vertex's low-link value equals its own discovery time, no vertex in its subtree can reach an ancestor, meaning the vertices on the stack above it form a complete SCC. This property enables the algorithm to emit SCCs incrementally without a second pass.

2. How It Works

Tarjan's algorithm is a depth-first search augmented with bookkeeping to track low-link values and a stack. It performs a single DFS over the entire graph, even if the graph is disconnected. For each unvisited vertex, it starts a recursive DFS call called strongconnect. This procedure assigns an index and low-link value, pushes the vertex onto a stack, and then explores all outgoing edges.

During edge exploration, three cases arise. If the neighbor w has not been visited, the algorithm recurses on w and then propagates its low-link value back: lowlink[v] = min(lowlink[v], lowlink[w]). This captures the ability to reach ancestors via the subtree rooted at w. If w has been visited and is currently on the stack, then (v, w) is a back edge to an ancestor in the current DFS path, so lowlink[v] = min(lowlink[v], index[w]). If w has been visited and is not on the stack, it already belongs to a completed SCC and is ignored, as it cannot affect the current component.

After exploring all neighbors, the algorithm checks if v is a root node. The condition lowlink[v] == index[v] indicates that v cannot reach any vertex discovered earlier than itself. At this point, all vertices above v on the stack belong to the same SCC as v. The algorithm pops vertices from the stack until v is removed, collecting them as one SCC. This process continues until all vertices are assigned.

The Role of the Stack and Low-Link

The stack is not the recursion stack, but an explicit stack that tracks the current DFS path plus any vertices that are strongly connected to that path. A vertex stays on the stack until its SCC root is found. The onStack boolean array allows O(1) checks to distinguish back edges to the current path from cross edges to already completed components. Without this distinction, the algorithm would incorrectly merge separate SCCs.

Low-link values are the core invariant. Formally, lowlink[v] is the smallest index of any vertex reachable from v through a path that consists of zero or more tree edges followed by at most one back edge. This definition ensures low-link values can be computed bottom-up during the DFS unwind phase. The monotonic propagation of minima guarantees that all vertices in the same SCC will eventually share the same low-link value as their root.

Condensation Graph Insight

Once all SCCs are found, contracting each SCC to a single node yields the condensation graph. This graph is always a DAG, which is a powerful property. Many NP-hard problems on general directed graphs become tractable on DAGs. Tarjan's algorithm implicitly produces SCCs in reverse topological order of the condensation graph, which is useful for dynamic programming and dependency resolution without an extra sorting step.

3. Implementation

Implementing Tarjan's algorithm correctly requires careful handling of indices, low-link updates, and stack management. The recursive version is concise and intuitive for most graph sizes in Python, though an iterative version is needed for very deep graphs to avoid recursion limits. Below is a clean, well-commented implementation that follows the classic formulation.

The graph is represented as an adjacency list where graph[v] contains a list of neighbors of vertex v. Vertices are assumed to be numbered 0 to n-1. The algorithm uses four auxiliary arrays: indices for discovery times, lowlink for low-link values, on_stack for stack membership, and stack for the explicit stack. The variable index is a global counter incremented on each discovery.

def tarjans_scc(graph):
    """
    Tarjan's Strongly Connected Components algorithm.
    graph: adjacency list, graph[v] = list of neighbors
    returns: list of SCCs, each SCC is a list of vertices
    """
    n = len(graph)
    index_counter = 0
    indices = [-1] * n
    lowlink = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []

    def strongconnect(v):
        nonlocal index_counter
        # Set discovery index and lowlink
        indices[v] = index_counter
        lowlink[v] = index_counter
        index_counter += 1
        stack.append(v)
        on_stack[v] = True

        # Explore successors of v
        for w in graph[v]:
            if indices[w] == -1:
                # Successor w has not yet been visited; recurse
                strongconnect(w)
                # Propagate lowlink from child
                if lowlink[w] < lowlink[v]:
                    lowlink[v] = lowlink[w]
            elif on_stack[w]:
                # Successor w is in stack => back edge
                if indices[w] < lowlink[v]:
                    lowlink[v] = indices[w]

        # If v is a root node, pop the stack to form an SCC
        if lowlink[v] == indices[v]:
            component = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)
                if w == v:
                    break
            sccs.append(component)

    for v in range(n):
        if indices[v] == -1:
            strongconnect(v)

    return sccs

For production systems or large graphs where recursion depth may exceed Python's default limit (typically 1000), an iterative implementation using an explicit call stack is preferred. This version simulates recursion by storing iterators and state, avoiding stack overflow while preserving the same logic.

def tarjans_scc_iterative(graph):
    """Iterative Tarjan to avoid recursion limits for large graphs."""
    n = len(graph)
    indices = [-1] * n
    lowlink = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    index_counter = 0

    # Explicit DFS stack: (v, iterator_index, child)
    for start in range(n):
        if indices[start] != -1:
            continue
        dfs_stack = [(start, 0, -1)]  # (vertex, next_neighbor_idx, parent)
        indices[start] = index_counter
        lowlink[start] = index_counter
        index_counter += 1
        stack.append(start)
        on_stack[start] = True

        while dfs_stack:
            v, nxt, parent = dfs_stack[-1]
            if nxt < len(graph[v]):
                w = graph[v][nxt]
                dfs_stack[-1] = (v, nxt + 1, parent)
                if indices[w] == -1:
                    indices[w] = index_counter
                    lowlink[w] = index_counter
                    index_counter += 1
                    stack.append(w)
                    on_stack[w] = True
                    dfs_stack.append((w, 0, v))
                elif on_stack[w]:
                    if indices[w] < lowlink[v]:
                        lowlink[v] = indices[w]
            else:
                # Finished processing v, propagate to parent
                dfs_stack.pop()
                if parent != -1:
                    if lowlink[v] < lowlink[parent]:
                        lowlink[parent] = lowlink[v]
                if lowlink[v] == indices[v]:
                    comp = []
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        comp.append(w)
                        if w == v:
                            break
                    sccs.append(comp)
    return sccs

Often you need more than just the list of components. The following helper builds the condensation DAG and maps each vertex to its component ID, which is essential for downstream tasks like topological sorting or 2-SAT solving.

def build_condensation(graph, sccs):
    """Build condensation DAG from SCCs."""
    n = len(graph)
    comp_id = [-1] * n
    for cid, comp in enumerate(sccs):
        for v in comp:
            comp_id[v] = cid

    m = len(sccs)
    condensed = [set() for _ in range(m)]
    indegree = [0] * m

    for v in range(n):
        for w in graph[v]:
            cv = comp_id[v]
            cw = comp_id[w]
            if cv != cw and cw not in condensed[cv]:
                condensed[cv].add(cw)
                indegree[cw] += 1

    # Convert sets to lists for easier use
    condensed = [list(s) for s in condensed]
    return condensed, comp_id, indegree

Finally, a utility to verify correctness and handle edge cases such as self-loops and isolated vertices is invaluable for testing.

def find_sccs_with_stats(graph):
    """Wrapper that returns SCCs and validates properties."""
    sccs = tarjans_scc(graph)
    # Verify partition: every vertex appears exactly once
    n = len(graph)
    seen = set()
    for comp in sccs:
        for v in comp:
            assert v not in seen, "Vertex in multiple SCCs"
            seen.add(v)
    assert len(seen) == n, "Not all vertices covered"

    # Count trivial vs non-trivial SCCs
    trivial = sum(1 for c in sccs if len(c) == 1)
    # Check for self-loop in trivial components
    non_trivial_trivial = 0
    for c in sccs:
        if len(c) == 1:
            v = c[0]
            if v in graph[v]:
                non_trivial_trivial += 1

    print(f"Found {len(sccs)} SCCs: {trivial} trivial, {len(sccs)-trivial} non-trivial")
    if non_trivial_trivial > 0:
        print(f"Note: {non_trivial_trivial} singleton SCCs have self-loops")
    return sccs

4. Step-by-Step Example

Consider a directed graph with 8 vertices (0-7) and the following edges: 0->1, 1->2, 2->0, 1->3, 3->4, 4->5, 5->3, 6->7, 7->6, 2->6, 5->7. This graph has three SCCs: {0,1,2}, {3,4,5}, and {6,7}. We will walk through Tarjan's execution starting from vertex 0.

Initialization sets all indices to -1 and index_counter to 0. The outer loop starts at vertex 0. strongconnect(0) assigns indices[0]=0, lowlink[0]=0, pushes 0, and explores neighbor 1. Since 1 is unvisited, it recurses. strongconnect(1) assigns indices[1]=1, lowlink[1]=1, pushes 1, and explores neighbor 2. strongconnect(2) assigns indices[2]=2, lowlink[2]=2, pushes 2. Vertex 2 has neighbors 0 and 6. Neighbor 0 is on the stack with index 0, so lowlink[2] becomes min(2,0)=0. Neighbor 6 is unvisited, so recurse to 6.

strongconnect(6) assigns indices[6]=3, lowlink[6]=3, pushes 6, explores 7. strongconnect(7) assigns indices[7]=4, lowlink[7]=4, pushes 7, explores 6. Since 6 is on stack with index 3, lowlink[7]=min(4,3)=3. After exploring, lowlink[7]=3 != indices[7]=4, so 7 is not a root and returns. Back in 6, lowlink[6] is updated to min(3,3)=3. Since lowlink[6]==indices[6]==3, 6 is a root. The algorithm pops until 6, yielding SCC {7,6} (order depends on stack). This SCC is emitted first, which is reverse topological order.

Returning to vertex 2, lowlink[2] is updated to min(0,3)=0. Vertex 2 finishes with lowlink[2]=0 != indices[2]=2, so it returns without emitting. Back in vertex 1, lowlink[1] becomes min(1,0)=0. Vertex 1 explores its next neighbor 3, which is unvisited. strongconnect(3) assigns indices[3]=5, lowlink[3]=5, pushes 3, explores 4. strongconnect(4) assigns indices[4]=6, lowlink[4]=6, pushes 4, explores 5. strongconnect(5) assigns indices[5]=7, lowlink[5]=7, pushes 5, explores 3 (on stack, index 5) so lowlink[5]=5, and explores 7 (not on stack, already assigned to completed SCC, ignored). Thus lowlink[5]=5 !=7, returns. Vertex 4 updates lowlink[4]=min(6,5)=5, returns. Vertex 3 updates lowlink[3]=min(5,5)=5. Since lowlink[3]==indices[3]==5, it pops {5,4,3} as the second SCC. Finally, vertices 1 and 0 unwind: lowlink[1] remains 0, lowlink[0] remains 0, and when 0 finishes, lowlink[0]==indices[0]==0, popping {2,1,0} as the final SCC. All vertices are now assigned.

Trace Summary

This walkthrough illustrates three key behaviors. First, SCCs are discovered in reverse topological order: {6,7} before {3,4,5} before {0,1,2}. Second, cross edges to already completed SCCs (like 5->7) are correctly ignored due to the on_stack check. Third, the root condition precisely identifies component boundaries without needing to know the full graph structure in advance. Visualizing the DFS tree with tree edges, back edges, and cross edges makes the low-link propagation intuitive.

5. Complexity Analysis

Tarjan's algorithm is asymptotically optimal for finding SCCs. It visits each vertex exactly once and examines each edge exactly once during the DFS. All auxiliary operations — stack pushes/pops, index assignments, and low-link updates — are O(1). Therefore, the total time complexity is linear in the size of the graph, O(V + E), where V is the number of vertices and E is the number of edges. This holds for best, average, and worst cases because the algorithm must inspect the entire graph to guarantee correctness; there is no early exit that avoids scanning edges.

Space complexity is O(V + E) for storing the graph as an adjacency list plus O(V) for auxiliary structures. The recursion stack can grow to O(V) in the worst case (a long path), and the explicit SCC stack also holds up to O(V) vertices. The indices, lowlink, and on_stack arrays each require O(V) space. For dense graphs where E is close to V², the adjacency list dominates memory usage, but the auxiliary overhead remains linear in V.

Compared to algorithms that require multiple passes, Tarjan's single-pass nature reduces constant factors and improves cache locality. The iterative variant trades a small overhead for explicit stack management to avoid recursion limits but retains the same asymptotic bounds. For sparse graphs typical in web and social networks, the linear time is crucial — O(V + E) scales to millions of vertices and edges where O(V²) would be infeasible.

It is worth noting that while the worst-case time is O(V + E), the practical performance depends on graph representation. An adjacency matrix would make edge iteration O(V²), degrading performance for sparse graphs. Always use an adjacency list. Additionally, Python recursion overhead can become significant for V > 10,000; in such cases, the iterative version or increasing recursion limits with sys.setrecursionlimit is necessary, though the latter still risks stack overflow in CPython.

6. Variations and Optimizations

Several variants of Tarjan's algorithm exist to address specific constraints. The most common is Kosaraju's algorithm, which is often taught as an alternative but is not a variation of Tarjan's — it uses two passes. True variations of Tarjan's include the path-based strong component algorithm (also by Gabow) and iterative implementations that eliminate recursion. Gabow's algorithm maintains two stacks instead of low-link values, using a second stack to track potential roots, which can be slightly faster in practice due to fewer array accesses.

For parallel and distributed settings, Tarjan's sequential DFS is inherently difficult to parallelize because DFS is P-complete. Researchers have developed divide-and-conquer approaches like the Forward-Backward (FW-BW) algorithm and coloring-based algorithms that trade some work efficiency for parallelism. These are used in large-scale graph processing frameworks such as GraphX and Pregel, where graphs exceed single-machine memory. However, for single-threaded execution, Tarjan's remains the gold standard.

Optimizations for Python include using iterative DFS, using arrays from the array module or list of ints for better cache performance, and early pruning for trivial SCCs. If you only need to know whether the graph is strongly connected (single SCC), you can terminate early when a second SCC is found, though this does not improve worst-case complexity. Another optimization is to use iterative deepening with explicit stacks and to store graph edges as contiguous lists to improve locality.

Handling Large Graphs

For graphs with millions of nodes, memory becomes the bottleneck. Techniques include using compressed sparse row (CSR) representation, memory-mapped files, and external DFS. Some implementations use iterative bitsets for on_stack to reduce memory. If the graph is streamed, semi-external algorithms that keep vertices in memory but edges on disk can be employed, though they sacrifice the single-pass guarantee.

Another practical variation is to combine SCC detection with topological sorting or cycle reporting. Since Tarjan's emits SCCs in reverse topological order, you can directly process them without building the condensation graph separately. For cycle detection, any SCC with more than one vertex or a self-loop indicates a cycle, allowing you to report cycles during the same traversal.

7. Real-World Applications

Strongly connected components are not just theoretical curiosities; they underpin critical infrastructure in software and systems. In compilers and build systems, dependency graphs must be acyclic to determine a valid compilation order. Tools like Make, Bazel, and npm use SCC detection to identify circular dependencies among modules. When a cycle is found, the system can report the exact set of files involved, helping developers break the cycle. Without SCC analysis, a build system might enter an infinite loop or produce incorrect builds.

In web search and social network analysis, SCCs reveal community structure. The web graph's SCC decomposition famously shows a bow-tie structure: a large SCC (the core), an IN component that can reach the core, an OUT component reachable from the core, and tendrils. Search engines like Google use this to prioritize crawling and to compute PageRank more efficiently — PageRank can be computed separately per SCC in topological order, accelerating convergence. Similarly, in social networks, SCCs identify tightly knit groups where information circulates freely.

Databases and formal verification rely heavily on SCCs. In deadlock detection, a wait-for graph tracks which transactions wait for which resources; a cycle (an SCC with >1 node) indicates deadlock. Databases use SCC detection to choose victims to abort. In model checking, the state transition graph of a system is analyzed for SCCs to verify liveness properties (e.g., "every request is eventually answered"). An SCC that is reachable and contains no accepting state may indicate a violation. The condensation DAG also enables efficient reachability indexing for graph databases like Neo4j.

One of the most elegant applications is solving 2-Satisfiability (2-SAT). Each Boolean variable and its negation become vertices, and each clause (a ∨ b) creates edges (¬a -> b) and (¬b -> a). The formula is unsatisfiable if and only if a variable and its negation lie in the same SCC. Tarjan's algorithm thus yields a linear-time 2-SAT solver, which is used in package managers, circuit design, and AI planning. This reduction showcases how SCC decomposition transforms a logical problem into a graph problem.

8. Comparison with Alternatives

While Tarjan's algorithm is optimal, it is not the only SCC algorithm. The two main alternatives are Kosaraju's algorithm and Gabow's path-based algorithm. Kosaraju's is conceptually simpler: it performs a DFS to compute finishing times, reverses the graph, and then performs a second DFS in decreasing finishing time order to collect SCCs. Gabow's algorithm is similar to Tarjan's but uses two stacks and avoids low-link arrays, which some benchmarks show to be slightly faster in low-level languages.

Brute-force approaches, such as running a DFS/BFS from each vertex to compute reachability and intersecting forward and reverse reachable sets, are O(V*(V+E)) and only feasible for tiny graphs. They are primarily of pedagogical interest to illustrate why linear-time algorithms are necessary. For interview purposes, understanding the trade-offs between Tarjan's and Kosaraju's is essential, as interviewers often ask you to implement one and discuss the other.

The choice between Tarjan's and Kosaraju's often comes down to implementation constraints. Tarjan's is more space-efficient and single-pass but is recursive and trickier to implement iteratively. Kosaraju's requires graph reversal (doubling memory or time) and two passes but is easier to parallelize for the second pass and easier to implement without recursion. Gabow's offers a middle ground with similar performance to Tarjan's but with different bookkeeping.

In practice, for Python, Kosaraju's is often preferred for its simplicity and to avoid subtle bugs with low-link updates, even though it uses more memory. For C++ or Java where recursion can be managed and performance is critical, Tarjan's or Gabow's may be faster due to better cache behavior and single-pass nature. Benchmarks on sparse graphs show all three linear algorithms perform similarly, with differences dominated by constant factors and graph representation rather than asymptotic complexity.

9. Common Mistakes and Best Practices

Implementing Tarjan's algorithm correctly is notoriously error-prone. The most common mistake is mishandling the low-link update for back edges. Developers often write lowlink[v] = min(lowlink[v], lowlink[w]) for both tree edges and back edges, when for back edges it should be min(lowlink[v], indices[w]). Using lowlink[w] for a back edge can incorrectly propagate values from a different SCC that has already been completed, leading to merged components that should be separate. The on_stack check is critical to avoid this.

Another frequent pitfall is forgetting to check on_stack[w] before updating low-link. Without this check, cross edges to already completed SCCs will incorrectly lower the low-link value, again merging distinct SCCs. Similarly, failing to initialize indices to -1 (or another sentinel) and instead using 0 can cause confusion between unvisited vertices and the first visited vertex. Always use a distinct sentinel and increment the global index counter correctly.

Recursion limits and stack overflow are practical issues in Python. A graph that is a long chain of 100,000 vertices will exceed the default recursion limit and crash with a RecursionError. Best practice is to either use the iterative version for large graphs or set sys.setrecursionlimit(10**6) and ensure the system stack can handle it. However, increasing recursion limits does not guarantee safety in CPython due to C stack limits; iterative is safer for production.

Best Practices Checklist

• Use adjacency lists, not matrices, for sparse graphs to maintain O(V+E) time.
• Maintain both indices and lowlink arrays; do not reuse one for the other.
• Always guard back-edge updates with if on_stack[w].
• Use indices[w] (not lowlink[w]) when updating from a back edge.
• Test with edge cases: empty graph, single vertex, self-loop, disconnected graph, complete DAG, and fully strongly connected graph.
• Verify that SCCs form a partition: every vertex appears exactly once and no vertex is lost.
• For large graphs, implement iterative DFS or use PyPy which has a larger stack.
• Profile memory: for n > 1e6, consider using array('i') or numpy for auxiliary arrays.

Testing is essential. Create a suite that includes a graph with no edges (n SCCs), a cycle covering all vertices (1 SCC), a DAG (n SCCs), and graphs with multiple SCCs connected in a DAG. Compare your output against a known correct implementation like Kosaraju's or NetworkX's strongly_connected_components for random graphs. This cross-validation catches subtle low-link bugs that unit tests with small graphs might miss.

10. Interview Questions

Tarjan's algorithm is a favorite in senior software engineering and advanced algorithms interviews. Interviewers use it to assess understanding of DFS, graph theory, and ability to implement non-trivial recursive algorithms. Below are common questions with guidance on how to answer them effectively.

Q1: Explain Tarjan's algorithm in plain English and why low-link values work.

Strong answer: Describe DFS discovery order, the stack of active vertices, and low-link as the earliest ancestor reachable via at most one back edge. Explain the root condition lowlink[v] == index[v] as detecting that no vertex in the subtree can reach above v, so the stack segment forms an SCC. Mention that low-link propagation via min ensures all vertices in an SCC share the root's low-link. Avoid just reciting code; explain the invariant and why the condensation graph is a DAG.

Q2: Implement Tarjan's or Kosaraju's to find SCCs and then determine if a directed graph has a cycle.

Strong answer: Implement either algorithm, then note that a directed graph has a cycle iff any SCC has size > 1 or a singleton SCC has a self-loop. Provide O(V+E) solution and discuss handling recursion limits. Bonus: show how to return the actual cycle by extracting one SCC with >1 node. Be prepared to code iteratively if asked to avoid recursion, and to analyze complexity.

Q3: How would you use SCCs to solve 2-SAT?

Strong answer: Construct the implication graph with 2n vertices (variable and its negation), add edges for each clause, run Tarjan's, and check if any variable and its negation are in the same SCC (unsatisfiable). If satisfiable, assign values in reverse topological order of SCCs: if comp[x] appears before comp[¬x], set x to false, else true. Explain why this works due to the condensation DAG's topological order and that Tarjan's already gives reverse order.

Q4: Compare Tarjan's vs Kosaraju's — when would you choose one over the other?

Strong answer: Discuss single-pass vs two-pass, need for graph reversal, space overhead, and implementation complexity. State that Tarjan's is more space-efficient and elegant but harder to implement iteratively; Kosaraju's is simpler and easier to get right, especially under interview pressure, but requires reversed graph. Mention that both are O(V+E) and choice is often about constraints like memory or need for iterative implementation. Mention Gabow's as an alternative if you know it.

Q5: Given a graph, find the minimum number of edges to add to make it strongly connected.

Strong answer: Find SCCs, build condensation DAG, count sources (indegree 0) and sinks (outdegree 0) in the DAG. If there is 1 SCC, answer is 0. Otherwise answer is max(sources, sinks). Explain reasoning: you need to connect sinks to sources to create a cycle covering all SCCs, and this is optimal. This tests ability to apply SCC decomposition to a higher-level problem and demonstrates understanding of DAG properties.

Preparing for these questions involves not just memorizing code but understanding the underlying DFS invariants, being able to trace an example, and knowing applications. Practice implementing both recursive and iterative versions, and be ready to discuss trade-offs, edge cases, and real-world uses to show depth beyond the algorithm itself.