Practice Problem: Given a directed graph, compress it into a condensation DAG. Find the length of the longest path in this DAG. Input: nodes, 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 . Process nodes in reverse topological order. Example: If the condensation graph is a chain , the longest path has length .