🎈 原创

消息的传递

我们的郭嘉大大在曹操这过得进遙自在, 但是有一天曹操给了他一个任务，在建邮城内有 N 个袁绍的奸细，将他们从 1 到 N 进行 编号, 同时他们之间存在一种传递关系, 即若 C**i,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

---

月初做的题到现在才开始补，什么叫懒癌晚期 XD

当时在考场上做的时候以为是道水题，直接敲了一个BFS交上去，结果就过了几个点，当时还天真的认为哪个细节没处理到位，现在看来是我根本没学到位。

这个图是有向图，边都是有方向的，不能用搜索的方法做。·

考虑这种情况，如果要有搜索做的话，答案就会是两个点（A，D），而实际情况是只要告诉D，其余的点就都会知道，所以不能简单地用搜索做。

看了网上看了题解以后才知道要用tarjan算法，这个我根本没听说过的玩意。

大致的思路就是用这个算法可以求出图中的各个强连通分量，也就是这几个点只要告诉一个其余的都会知道。利用这个将整张图分成几个部分，最后统计一下哪几个部分入读为0，也就是这几个部分必须要主动告诉，否则不会被传递到。

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

const int maxN = 2020;
int N, dfn[maxN], low[maxN], time = 0;
int Graph[maxN][maxN] = {0}, nodeIndex[maxN] = {0}, cnt = 0;
stack<int> S;
bool inStack[maxN] = {false};

void tarjan(int u);     //tarjan缩点

int main(int argc, const char * argv[])
{
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> Graph[i][j];     //输入图

    for(int i = 0; i < N; i++)
        if(!dfn[i])         //Time从1开始递增，所以可以用dfn是否为0来判断该点是否被访问过
            tarjan(i);

    int indegrees[cnt];     //统计每个连通分量的入度
    for(int i = 0; i < cnt; i++)
        indegrees[i] = 0;   //局部变量的数组一定要初始化！！

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(Graph[i][j])
            {
                if(nodeIndex[i] != nodeIndex[j])    //两个节点不属于同一个连通分量
                    indegrees[nodeIndex[j]]++;
            }

    int ans = 0;
    for(int i = 0; i < cnt; i++)
        if(indegrees[i] == 0)   //统计入度为0的连通分量
            ans++;

    cout << ans << endl;

    return 0;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++time;
    S.push(u);
    inStack[u] = true;
    for(int v = 0; v < N; v++)
        if(Graph[u][v])
        {
            if(!dfn[v])
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if(inStack[v])
                low[u] = min(low[u], low[v]);
        }
    if(dfn[u] == low[u])
    {
        while(S.top() != u)
        {
            nodeIndex[S.top()] = cnt;
            inStack[S.top()] = false;
            S.pop();
        }
        nodeIndex[S.top()] = cnt;
        inStack[S.top()] = false;
        S.pop();
        cnt++;
    }

}