题目描述(ID:12207)
标题: 收集宝石
标签: 图结构 二分图 二分图匹配 网络流
详情: 在AHA CODE PLANET中有n个宝石,这个n个宝石组成了一个有向无环图,现在你需要收集这些宝石,AHA CODE PLANET SHOP 中的道具炉石可以帮助空降在任意一个地点,即任意选择一个起点开始,进行收集。现在请问你至少需要从AHA CODE PLANET SHOP 购买多少个炉石。可以帮你采集所有的宝石。注意每个点只能走一次。
输入格式:
第 1 行有 2 个正整数 n 和 m 。n是给定有向无环图 G 的顶点数,m 是 G 的边数。
接下来的 m 行,每行有 2 个正整数 u 和 v ,表示一条有向边 (i,j) 。
输出格式:
一个整数X表示最少需要的炉石数量
限制: 1≤n≤200,1≤m≤6000
样例:

输入

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

输出

3

解释

1 4 7 10 11
2 5 8
3 6 9
登录并解答