#z1050. 明星
明星
【问题描述】
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己。奶牛之间的“喜欢”是可以传递的——如果 A 喜欢 B,B 喜欢 C,那么 A 也喜欢 C。牛栏里共有 n 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。
【输入格式】
第一行两个正整数 n,m,表示奶牛数和给定的爱慕关系数。 接下来的 m 行,每行 2 个正整数 ai,bi,表示奶牛 ai 喜欢奶牛 bi。
【输出格式】
一行一个整数,表示明星奶牛的数量。
【输入样例】 3 3 1 2 2 1 2 3 【输出样例】 1 【样例解释】
只有 3 号奶牛是明星奶牛。
【数据规模和约定】
- 对于 30% 的数据,保证 n≤20,m≤50。
- 对于 70% 的数据,保证 n≤1000,m≤104。
- 对于 100% 的数据,保证 n≤105,m≤5×105。
相关
在下列比赛中: