本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-08 15:15:17

最小路径覆盖就是选出最少数量的互不重合的路径，使其包含所有的点。也即，每个点在且仅在一条路径上头。

题解区队爷提到：对于这种“对于每个，有且只有”的性质，可以抽象成二分图。

每个点与两个点连接，分别是作为入点和出点的情况。那么我们考虑把每个点抽象成两个点 $(u, u + n)$，然后向 $u$ 的每个出点连边 $(u + n, v)$。这样，我们就能求出来合并的数量，以 $n$ 减去就是路径数量。