这个题就是tarjan强连通分量与入度的例题了。
思路：
利用缩点的思想，先预处理一下所有的强连通分量，然后把每个强连通分量内的所有节点看做一个节点，然后处理一张新图，然后检查每个点的入度，然后取入度为 0 的点（缩点后）的个数，即为信息出发点。
可能有人想问为什么？？
大体说明一下：
1.充分性证明：如果入度为 0 的点不是信息出发点，那么这个点必定不会接收到任何节点发出的信息，因为它的入度为 0 。
2.必要性证明：如果信息出发点不是入度为0的点，那么其必有入度点，使其覆盖点更多，而我们要找至少多少个点。
还是先明确一下各个数组的意思吧：
dfn[i]:i点的时间戳 low[i]，表示这个点以及其子孙节点连的所有点中dfn最小的值 stack[]，表示当前所有可能能构成是强连通分量的点。 ins[i]，表示 i 是否在stack[ ]数组中 num[i],表示第 i 个强连通分量中有多少个点 belong[i],表示第 i 点在哪一个强连通分量里 in[i]:表示第 i 个强连通分量的入度是多少。
以下就是怎么处理入度：
for(int i=1;i<=m;i++){ if(belong[edge[i].from] != belong[edge[i].to]) in[belong[edge[i].to]]++; } 解释一下：
枚举边，比较这条边起点和终点是否在同一个强连通分量中，如果不在，这条边终点的入度++
AC代码：
#include#include #include #include using namespace std;const int maxn = 1e5 + 5;const int maxm = 5e5 + 6;int n,m,u,v;int head[maxn],tot;int dfn[maxn],low[maxn],ind;int stack[maxn],top,belong[maxn],num[maxn],cnt;int in[maxn];//表示某个点的入度 int ans;bool ins[maxn];struct Edge{ int from,to,next;}edge[maxm]; void add(int u,int v){ edge[++tot].to = v; edge[tot].from = u; edge[tot].next = head[u]; head[u] = tot;}int read(){ char ch = getchar(); int f = 1 , x = 0; while(ch > '9' || ch < '0'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f;}void tarjan(int x){ dfn[x] = low[x] = ++ind; stack[++top] = x; ins[x] = true; for(int i=head[x];i;i=edge[i].next){ int v = edge[i].to; if(ins[v]) low[x] = min(low[x] , dfn[v]); if(!dfn[v]){ tarjan(v); low[x] = min(low[v] , low[x]); } } int k; if(dfn[x] == low[x]){ ++cnt; do{ k = stack[top]; num[cnt]++; top--; ins[k] = false; belong[k] = cnt; } while(k != x); }}int main(){ n = read(); m = read(); for(int i=1;i<=m;i++){ u = read(); v = read(); add(u , v); } for(int i = 1;i <= n ;++i) belong[i] = i; for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=m;i++){ if(belong[edge[i].from] != belong[edge[i].to]) in[belong[edge[i].to]]++; } for(int i=1;i<=cnt;i++) if(in[i] == 0) ans++; printf("%d\n",ans); return 0;}