题目地址：

https://www.acwing.com/problem/content/1178/

我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有$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\le N\le 1000$

可以先求强连通分量并缩点，然后求入度为$0$的强连通分量有多少个，这些分量互相不可达，并且只需要他们知道了消息，就能使得所有人都知道消息。代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int n;
bool g[N][N];
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], din[N], scc_cnt;
bool in_stk[N];

void tarjan(int u) {
  dfn[u] = low[u] = ++timestamp;
  stk[top++] = u, in_stk[u] = true;
  for (int v = 1; v <= n; v++)
    if (g[u][v]) {
      if (!dfn[v]) {
        tarjan(v);
        low[u] = min(low[u], low[v]);
      } else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
    }
  
  if (dfn[u] == low[u]) {
    int y;
    scc_cnt++;
    do {
      y = stk[--top];
      in_stk[y] = false;
      id[y] = scc_cnt;
    } while (y != u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      scanf("%d", &g[i][j]);

  for (int i = 1; i <= n; i++)
    if (!dfn[i])
      tarjan(i);
  
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (g[i][j] && id[i] != id[j])
        din[id[j]]++;

  int res = 0;
  for (int i = 1; i <= scc_cnt; i++) 
    if (!din[i]) res++;

  printf("%d\n", res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

时间复杂度$O(N^2)$，空间$O(N)$。