问题 L: 确定排名
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
题目描述
在一个班级里,有 n
名学生,他们刚经历了一场考试,由于分数没有公开,所以无法确定每个人的排名。
小爱通过私下交流,得到 m 条线索,其中第 i 条线索可以确定,第 xi
号学生的分数高于第 yi
号学生。又可以确认,没有任何两个学生的分数是相同的。那么根据这些线索,小爱可以确定多少学生的分数的名次呢?保证线索不会产生矛盾。
输入格式
第一行:两个整数 n 和 m;
第二行到第m+1
行:第i+1
行有两个整数 xi
和 yi
,表示第 xi
号学生的分数高于第 yi
号学生。
输出格式
单个整数:表示可以确定多少学生的名次。
数据范围
1≤m≤n(n−1)/2
对于 30% 的数据,1≤n≤12
;
对于 60% 的数据,1≤n≤50
;
对于 100% 的数据,1≤n≤300
。
样例数据
输入:
5 4
1 3
2 3
3 4
3 5
输出:
1
说明:
1
与2高于3,3又高于4与5,所以只有3的排名是确定的