最小路径覆盖问题

【题目描述】

给定有向图$G=(V,E)$。设$P$是$G$的一个简单路（顶点不相交）的集合。如果$V$中每个顶点恰好在$P$的一条路上，则称$P$是$G$的一个路径覆盖。$P$中路径可以从$V$的任何一个顶点开始，长度也是任意的，特别地，可以为$0$。$G$的最小路径覆盖是$G$的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图$G$的最小路径覆盖。

【提示】

设$V={1，2，... ，n}$，构造网络$G_1$=$(V_1,E_1)$如下：

每条边的容量均为$1$。求网络$G_1$的$(x_0,y_0)$最大流。

【输入格式】

第$1$行有$2$个正整数$n$和$m$。$n$是给定有向无环图$G$的顶点数，$m$是$G$的边数。

接下来的$m$行，每行有$2$个正整数$i$和$j$，表示一条有向边$(i,j)$。

【输出格式】

从第$1$行开始，每行输出一条路径。文件的最后一行是最少路径数。

【输入样例】

11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

【输出样例】

1 4 7 10 11
2 5 8
3 6 9
3

【数据范围】

$1<=n<=150,1<=m<=6000$；

【来源】

算法实现题$8-3$ 最小路径覆盖问题（习题$8-13$）