/ Vijos / 题库 /

明星学生

明星学生

时间限制:1秒  内存限制:256M


【题目描述】

  正是青春萌动的年龄,每位同学都梦想成为学校里令人瞩目的明星。被所有其他同学喜欢的同学才算是明星学生。同学之间的“喜欢”是可以传递的:如果 \(a\) 喜欢 \(b\),\(b\) 喜欢 \(c\),那么 \(a\) 也喜欢 \(c\)。学校里共有 \(N\)名同学,给定一些同学之间的“喜欢”关系,请你算出有多少名同学可以当明星学生。

【输入格式】

  第一行:两个用空格分开的整数:\(n\) 和 \(m\),\(n\) 名学生编号为 \(1..n\)。
  接下来 \(m\) 行:每行两个用空格分开的整数:\(a\) 和 \(b\),表示 \(a\) 喜欢 \(b\)。

【输出格式】

  输出一行单独一个整数,表示明星学生的数量。

【输入输出样例1】

 Input

3 3
1 2
2 1
2 3

 Output

1

【样例1解释】

  1和2相互喜欢,2又喜欢3,所以1也喜欢3,因此3号同学是明星学生。

【输入输出样例2】

 Input

10 12
1 2
1 4
2 5
3 4
4 5
5 6
6 10
7 8
8 9
9 10
10 5
7 9

 Output

3

【样例2解释】

  本样例中5、6和10号同学是明星学生。

【测试点性质】

  对于10% 的数据,\(N≤20,M≤50\)。
  对于30% 的数据,\(N≤1000,M≤20000\)。
  对于70% 的数据,\(N≤5000,M≤50000\)。
  对于100% 的数据,\(1≤N≤10000,1≤M≤50000\)。

【来源】

  Mr.he

信息

ID
3235
难度
(无)
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
3
上传者