PreviousNext
Coding/Graphs and trees

Condensation DAG source nodes

Write codeHard40 min

Your task

Given a directed graph with n nodes (0..n-1) and edges [u, v], collapse each strongly connected component into a single super-node to form the condensation DAG. Return the number of source super-nodes (components whose in-degree in the condensation is zero). These are the minimum set of components you'd have to 'seed' to reach the whole graph. Constraints: 1 <= n <= 2000.

Examples

count_condensation_sources(n: int, edges: list[list[int]]) -> int
Example 1
Inputcount_condensation_sources(5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]])
Output1