[SDOI2007]环球旅行问题

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 chbtrip.in 输出文件 chbtrip.out
【问题描述】
关于哈密顿道路问题大家一定很熟悉吧。该问题和哈密顿问题类似，也是关于环球旅行
的，但是该问题与哈密顿问题不同的是，该题不是 NP 问题。
地球上有 n 个城市，这些城市之间有 m 条单向的道路，这些道路之间不存在回路
（环）。现在CHB 先生想进行多次环球旅行，每次旅行可以在任意城市出发，当然，可以
在任意城市结束。但是，在所有的旅行过程中，不能经过同一城市两次或多于两次。
问题是：
CHB 先生最少需要多少次旅行，才能到达所有的城市？
【输入】(trip.in)
第一行 n m。
以下 m 行，每行两个数 u v，表示 u 到 v 之间有一条路。顶点标号为：0 到n-1
【输出】(trip.out)
最少的旅行次数。
【样例输入】
5 8
4 3
3 2
0 3
4 2
4 0
1 2
0 2
1 0
【样例输出】
2
范围：前 30 ％数据，1 <=n<= 50 m<=200
全部数据 1 <= n <= 500 m <= 5000