1084. Minimum Path Cover in DAG

Given a directed acyclic graph with n nodes and edges, return the minimum number of vertex-disjoint directed paths needed to cover all vertices (each vertex on exactly one path). This equals n minus the maximum bipartite matching of the split graph. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the minimum number of paths.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3]]}
Output: 1
Explanation: A single path covers all.

Input: {"n":3,"edges":[[0,1],[0,2]]}
Output: 2
Explanation: Two paths from the branch.

Input: {"n":4,"edges":[]}
Output: 4
Explanation: Each node its own path.

Constraints

• 1<=n<=500
• directed acyclic

Asked by