灯塔——高级
1 Sec 64 MB |
40 | 152 |
通过 | 提交 |
题目描述
灯塔是建于航道关键部位附近的一种塔状发光航标。灯塔是一种固定的航标,用以引导船舶航行或指示危险区。
同时,灯塔也可以用于相互间传递信息(如用灯光打出摩斯码)。但是,由于灯塔年久失修,所能转动的角度有限,如A能照到B,而反过来却不一定。
现在海上出现了一股台风,需要尽快通知所有的灯塔。已知每个灯塔可以到照到的其他灯塔,由于时间紧迫,最少通知多少灯塔就
可以通过他们之间的信息传递使得所有灯塔都得到消息?
输入格式
第一行两个整数N,M(1<=N<=100,000 0<=M<=1,000,000)表示灯塔个数和可以照到灯光的关系数。
接下来M行,每行两个整数A,B(1<=A,B<=N)表示灯塔的编号,灯塔A可以照到灯塔B。
输出格式
输出最少通知多少灯塔就可以通过他们之间的信息传递使得所有灯塔都得到消息
样例输入 #1
4 2 1 2 1 3 4 2 2 1 3 1
样例输出 #1
2 3
提示
Case 1: 只需要通知1和4,2和3由1转发。
Case 2: 需要通知2,3,4,1可以从2或者3得到消息。