问题2077--奶牛排序

2077: 奶牛排序

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

约翰想按照奶牛的产奶能力给它们排序。已知有N （1≤N ≤1 000 ） 头奶牛， 而且知道这些奶牛的M（1≤M ≤10 000）种关系，将每种关系都表示为“X Y ”，表示奶牛X 的产奶能力大于奶牛Y 。约翰想知道自己至少还要调查多少对关系才能完成整个排序。

输入

第1行包含两个整数N 和M 。第2…M +1行，每行都包含两个整数X 和Y 。X 和Y 都在1～N 范围内，表示奶牛X 的排名高于奶牛Y 。

输出

单行输出至少还要调查多少种关系才能完成整个排序。

样例输入 Copy 

5 5
2 1
1 5
2 3
1 4
3 4

样例输出 Copy 

3

来源/分类

图论基础 
[提交] [状态]