2743: 最小路径覆盖
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
一个有向无回路的图G＝(V，E)的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的一条路径。路径可从任意结点开始和结束，且长度也为任意值，包括0。请写出一个有效算法，找出一个包含尽可能少的路径的路径覆盖。 例如下图至少用两条路径覆盖，路径可以是：1-5-3，2-4。
输入
第一行为n(n≤4000)，表示图G的顶点个数，从第二行开始每行有两个数u,v表示存在边（u,v）。
输出
第一行为所求的最少的路径覆盖数k。第二行至第k+1行为每条路径上以0结尾的顶点序列。
样例输入 复制
5
1 2
1 5
2 3
2 4
5 3
样例输出 复制
2
1 5 3 0
2 4 0