Condensation DAG source nodes
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.
Implement
count_condensation_sources(n: int, edges: list[list[int]]) → intExamples
in
[5,[[0,1],[1,2],[2,0],[1,3],[3,4]]]out1What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 40 min
solution.py
InputExpectedGot
[5,[[0,1],[1,2],[2,0],[1,3],[3,4]]]1not run yetsample