【题目描述】

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

。

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

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

）。
【输出】

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

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

【输出样例】

2

【提示】

数据范围与提示：

N≤1000
模板题
入度为0就需要给它提供消息

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000 + 10;
int f[N][N];
int n;
int dfn[N], low[N] ,timestamp;
int stk[N], in_stk[N], top;
int id[N], scc_cnt;
int din[N], dout[N];


void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u; in_stk[u] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(f[u][i])
        {
            if(!dfn[i])
            {
                tarjan(i);
                low[u] = min(low[u], low[i]);
            }
            else if(in_stk[i])
            {
                low[u] = min(low[u], dfn[i]);
            }
        }
    }

    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            id[y] = scc_cnt;
            in_stk[y] = 0;
        }while(y != u);
    }

}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        for(int j = 1 ;j <= n; j++)
            scanf("%d",&f[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(i == j) continue;
            if(!f[i][j]) continue;
            if(id[i] != id[j])
            {
                din[id[j]]++;
            }
        }
    }
    int a = 0, b = 0;
    for(int i = 1; i <= scc_cnt; i++)
    {
        if(!din[i]) a++;
    }
    printf("%d",a);
    return 0;
}