P2764 Minimum Path Cover Problem

Given a directed graph $G=(V,E)$. Let $P$ be a set of simple paths (vertex-disjoint) in $G$. If every vertex in $V$ appears in exactly one path in $P$, then $P$ is a path cover of $G$. Paths in $P$ can start at any vertex in $V$, and their lengths are arbitrary; in particular, the length can be $0$. The minimum path cover of $G$ is a path cover with the fewest number of paths. Design an efficient algorithm to find a minimum path cover of a DAG (directed acyclic graph) $G$.

The first line contains two positive integers $n$ and $m$. Here $n$ is the number of vertices of the given DAG (directed acyclic graph) $G$, and $m$ is the number of edges of $G$. The next $m$ lines each contain two positive integers $i$ and $j$, representing a directed edge $(i, j)$.

Starting from the first line, output one path per line. The last line of the file is the minimum number of paths.

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 150$, $1 \leq m \leq 6000$. SPJ provided by @FlierKing. Translated by ChatGPT 5