1516：消息的传递

题目描述

我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有 $N$ 个袁绍的奸细，将他们从 $1$ 到 $N$ 进行编号，同时他们之间存在一种传递关系，即若 $C_{i,j}=1$，则奸细 $i$ 能将消息直接传递给奸细 $j$。

现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细？

输入格式

第一行为 $N$，第二行至第 $N+1$ 行为 $N \times N$ 的矩阵（若第 $I$ 行第 $J$ 列为 $1$，则奸细 $I$ 能将消息直接传递给奸细 $J$，若第 $I$ 行第 $J$ 列为 $0$，则奸细 $I$ 不能将消息直接传递给奸细 $J$）。

输出格式

只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

样例

样例输入 #1

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

样例输出 #1

2

样例解释 #1

• $N=8$ 个奸细。
• 传递关系矩阵：
  • 奸细 $1$ 能传给 $3$。
  • 奸细 $2$ 能传给 $1$ 和 $4$。
  • 奸细 $3$ 能传给 $2$、$4$、$5$。
  • 奸细 $4$ 能传给 $6$。
  • 奸细 $5$ 能传给 $4$。
  • 奸细 $6$ 能传给 $4$。
  • 奸细 $7$ 能传给 $4$ 和 $8$。
  • 奸细 $8$ 能传给 $7$。
• 需要选择最少的奸细作为初始传递点，使得消息能通过直接或间接传递到达所有奸细。
• 可以将消息初始传给奸细 $2$ 和奸细 $7$：
  • 奸细 $2$ 传给 $1$ 和 $4$，$1$ 传给 $3$，$3$ 传给 $2$（已传）和 $5$，$4$ 传给 $6$。
  • 奸细 $7$ 传给 $4$（已传）和 $8$。
• 所有奸细都被覆盖。无法用 $1$ 个初始点覆盖所有，所以至少需要 $2$ 个。

数据范围

• $N \le 1000$

时空限制

• 时间限制：1000 ms
• 内存限制：562144 KB

注意：本题是有向图的最小点基（最小反馈点集？）问题，实际上是求有向图的强连通分量缩点后，入度为 $0$ 的强连通分量个数（因为每个入度为 $0$ 的强连通分量必须至少有一个点作为初始传递点，否则无法从其他分量传入）。因此，任务就是计算强连通分量缩点后入度为 $0$ 的节点个数。由于 $N \le 1000$，可以使用 Tarjan 算法求强连通分量，然后统计入度。注意矩阵输入较大，需使用快速读入。