B. 确定排名

    传统题 1000ms 256MiB

确定排名

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个班级里,有 nn 名学生,他们刚经历了一场考试,由于分数没有公开,所以无法确定每个人的排名。

小爱通过私下交流,得到 mm 条线索,其中第 ii 条线索可以确定,第 xix_i 号学生的分数高于第 yiy_i 号学生。又可以确认,没有任何两个学生的分数是相同的。那么根据这些线索,小爱可以确定多少学生的分数的名次呢?保证线索不会产生矛盾。

输入格式

第一行:两个整数 nnmm; 第二行到第 m+1m+1 行:第 i+1i+1 行有两个整数 xix_iyiy_i,表示第 xix_i 号学生的分数高于第 yiy_i 号学生。

输出格式

单个整数:表示可以确定多少学生的名次。

5 4
1 3
2 3
3 4
3 5
1

样例解释 1

1 与 2 高于 3,3 又高于 4 与 5。 因此,只有学生 3 的排名是确定的(第 3 名)。

数据规模与约定

1mn(n1)/21 \leq m \leq n(n-1)/2

对于 3030% 的数据,1n121 \leq n \leq 12

对于 6060% 的数据,1n501 \leq n \leq 50

对于 100100% 的数据,1n3001 \leq n \leq 300

图灵寒假比赛十一

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-2-11 21:00
结束于
2026-2-12 2:00
持续时间
5 小时
主持人
参赛人数
7