【题目链接】
ybt 1516：消息的传递
【题目考点】
1. 图论：强连通分量，有向图缩点
【解题思路】
每个奸细是一个顶点，如果i能将消息传递给j，则从顶点i到顶点j有一条有向边。
有向图中强连通分量中的顶点之间都有路径，也就是在一个强连通分量中的顶点所表示的奸细之间都可以互相直接或间接地传递消息。只要该强连通分量中的一个顶点接收到消息，整个强连通分量中的顶点都会接收到消息。
如果一个强连通分量中的顶点可以接收到消息，那么从该强连通分量出发的边所指向的另一个强连通分量中的顶点也能接收到消息。
因此可以进行缩点操作。使用求强连通分量的算法（Kosaraju算法或Tarjan算法），求出有向图中的所有强连通分量，将每个强连通分量看做一个顶点，进行缩点，缩点后一定会得到一个有向无环图。
缩点后的图中，只需要向每个入度为0的顶点传递消息，那么每个顶点都会收到消息。
因此该题所求的就是在缩点后的图中入度为0的顶点的数量，或原图中入度为0的强连通分量的数量。
具体操作时可以不用真的建立缩点后的图，只需要对强连通分量进行入度统计即可。
【题解代码】
解法1：Tarjan算法求强连通分量 缩点 邻接表
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int dfn[N], low[N], ts;//dfn[i]：顶点i的时间戳 low[i]：顶点i通过有向边能回溯到的最早时间戳 ts：时间戳
int n, scc[N], sn, degIn[N];//scc[i]：顶点i所属的强连通分量 degIn[i]：强连通分量i的入度
stack<int> stk;
vector<int> edge[N];
bool inStk[N];//顶点i是否在栈中
void tarjan(int u)
{int t;dfn[u] = low[u] = ++ts;stk.push(u);inStk[u] = true;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);}else if(inStk[v])low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){++sn;do{t = stk.top();stk.pop();scc[t] = sn;inStk[t] = false;}while(t != u);}
}
int main()
{int a, ct = 0;cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){cin >> a;if(a == 1)edge[i].push_back(j);}for(int v = 1; v <= n; ++v) if(dfn[v] == 0)tarjan(v);for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(scc[u] != scc[v])degIn[scc[v]]++;for(int i = 1; i <= sn; ++i) if(degIn[i] == 0)ct++;cout << ct;return 0;
}
解法2：Kosaraju算法求强连通分量 缩点 邻接矩阵
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n, g[N][N], rg[N][N], degIn[N];//g：正图 rg：反图 degIn[i]：强连通分量i的入度
int scc[N], sn;//scc[i]：顶点i所属的强连通分量编号 sn：强连通分量个数
stack<int> stk;
bool vis[N];
void dfs_rg(int u)
{vis[u] = true;for(int v = 1; v <= n; ++v) if(rg[u][v] && !vis[v])dfs_rg(v);stk.push(u);
}
void dfs_g(int u)
{vis[u] = true;scc[u] = sn;for(int v = 1; v <= n; ++v) if(g[u][v] && !vis[v])dfs_g(v);
}
void kosaraju()
{for(int v = 1; v <= n; ++v) if(!vis[v])dfs_rg(v);memset(vis, 0, sizeof(vis));while(!stk.empty()){int v = stk.top();stk.pop();if(!vis[v]){++sn;dfs_g(v); }}
}
int main()
{int a, ct = 0;cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){cin >> a;g[i][j] = rg[j][i] = a;}kosaraju();for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) if(g[i][j] && scc[i] != scc[j])degIn[scc[j]]++;for(int i = 1; i <= sn; ++i) if(degIn[i] == 0)ct++;cout << ct;return 0;
}