Practice Problem 2

Practice Problem: Given a directed graph, compress it into a condensation DAG. Find the length of the longest path in this DAG. Input: $n$ nodes, $m$ directed edges. Output: Longest path length (number of edges). Hint: Run SCC detection to find all components.

Build the condensation graph. Run DP: dp[v] = 1 + max(dp[u]) for all edges $v \to u$. Process nodes in reverse topological order. Example: If the condensation graph is a chain $A \to B \to C$, the longest path has length $2$.