PreviousNext
Coding/Graphs and trees

Minimum path cover DAG

Write codeHard45 min

Your task

Given a directed acyclic graph with n nodes (0..n-1) and edges [u, v], find the minimum number of vertex-disjoint directed paths needed to cover every vertex exactly once (a single vertex with no edges is a path of length zero). Return that minimum count. The input is guaranteed acyclic. Constraints: 1 <= n <= 300.

Examples

min_path_cover_dag(n: int, edges: list[list[int]]) -> int
Example 1
Inputmin_path_cover_dag(3, [[0, 1], [1, 2]])
Output1