有n个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出n个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有n个城市都得到消息。
前置知识：
分析
会了强联通分量以后呢，我们可以开始写这道题了。首先这道题不是一个 (DAG) 我们应该先缩点，把这个图变成一个 (DAG)。
变成 (DAG) 就好了，我们就可以记录每个点的入度，答案即为所有入度为 (0) 的点的个数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
template<typename T>inline void write(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar('0'+x%10);
}
const int MAXN=1e6+10,MAXM=1e6+10;
int s[MAXN], stop,dfn[MAXN],low[MAXN],scccnt, sccnum[MAXN],dfscnt,tot,he[MAXN],ne[MAXM<<1],ed[MAXM<<1],n,x,y,de[MAXN],ans,m;
void add(int x,int y){
ed[++tot]=y;
ne[tot]=he[x];
he[x]=tot;
}
inline void tarjan(int now){
dfn[now] = low[now] = ++dfscnt;
s[stop++] = now;
for (int i = he[now]; i; i = ne[i]){
if(!dfn[ed[i]]){
tarjan(ed[i]);
low[now] = min(low[now], low[ed[i]]);
}else if(!sccnum[ed[i]]) {
low[now] = min(low[now], dfn[ed[i]]);
}
}
if (dfn[now]==low[now]){
scccnt++;
do {
sccnum[s[--stop]]=scccnt;
}while(s[stop]!=now);
}
}
int main(){
read(n);read(m);
for(int i=1;i<=m;i++){
read(x);read(y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
for(int j=he[i];j;j=ne[j])
if(sccnum[i]!=sccnum[ed[j]])de[sccnum[ed[j]]]++;
for(int i=1;i<=scccnt;i++)
if(!de[i])ans++;
cout<<ans;
return 0;
}