消息的传递
消息的传递
我们的郭嘉大大在曹操这过得进遙自在, 但是有一天曹操给了他一个任务,在建邮城内有 N 个袁绍的奸细,将他们从 1 到 N 进行 编号, 同时他们之间存在一种传递关系, 即若 C**i,j=1, 则奸细 i 能将消息直接传递给奸细 j。
现在曹操要发布一个假消息, 需要传达给所有奸细,而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息, 问我们至少要传给几个奸细?
输入格式:
第一行为 N, 第二行至第 N+1 行为 N×N 的矩阵 ( 若第 I 行第 J 列为 1, 则奸细 I 能将消息直接传递给奸细 J, 若第 I 行第 J 列为 0 , 则奸细 I 不能将消息直接传递给奸细 J) 。
输出格式:
只有一行:即我们的郭嘉大大首先至少要传递的奸细个数。
输入样例:
1 | 8 |
输出样例:
1 | 2 |
数据范围与提示
N≤1000