PreviousNext
Coding/Graphs and trees

Longest SCC chain

Write codeHard35 min

Your task

Given a directed graph with n nodes (0..n-1) and a list of directed edges, condense it into its strongly connected components. In the resulting condensation DAG (one super-node per SCC), return the maximum number of SCCs lying on a single directed path (i.e. the length, in nodes, of the longest chain of components). A graph that is itself one SCC has answer 1. Assume 1 <= n <= 5000.

Examples

scc_condensation_longest_chain(n: int, edges: list[list[int]]) -> int
Example 1
Inputscc_condensation_longest_chain(5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]])
Output3