/ Randle / 题库 /

BOMB炸弹(CQ直辖市noip模拟赛联考) T1

BOMB炸弹(CQ直辖市noip模拟赛联考) T1

【题目描述】
战狂也在玩《魔方王国》。他只会征兵而不会建城市,因此他决定对小奇的
城市进行轰炸。
小奇有 n 座城市,城市之间建立了 m 条有向的地下通道。战狂会发起若干
轮轰炸,每轮可以轰炸任意多个城市。
每座城市里都有战狂部署的间谍,在城市遭遇轰炸时,它们会通过地下通道
撤离至其它城市。非常不幸的是,在地道里无法得知其它城市是否被轰炸,如果
存在两个不同的城市 i,j,它们在同一轮被轰炸,并且可以通过地道从城市 i 到
达城市 j,那么城市 i 的间谍可能因为撤离到城市 j 而被炸死。为了避免这一情况,
战狂不会在同一轮轰炸城市 i 和城市 j。
你需要求出战狂最少需要多少轮可以对每座城市都进行至少一次轰炸
【输入数据】
第一行两个整数 n,m。接下来 m 行每行两个整数 a,b 表示一条从 a 连向 b
的单向边。
【输出数据】
输出一行仅一个整数表示答案。
【样例输入输出】
bomb.in
5 4
1 2
2 3
3 1
4 5
bomb.out
3
【数据范围】
对于 20%的数据,n,m<=10。
对于 40%的数据,n,m<=1000。
对于另外 30%的数据,保证无环。
对于 100%的数据,n,m<=1000000。
【对于看不懂题目的同学】这个题目确实有问题,反正就是先缩点,再找最长链(按权值计算)。对于环缩成的点,点权为它的大小。

信息

难度
9
分类
(无)
标签
(无)
递交数
18
已通过
2
通过率
11%
上传者