题目背景
本场比赛第一题，给个简单的吧，这 100 分先拿着。
题目描述
有n个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出n个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有n个城市都得到消息。
输入输出格式
输入格式：
第一行两个整数n,m表示n个城市，m条单向道路。
以下m行，每行两个整数b,e表示有一条从b到e的道路，道路可以重复或存在自环。
输出格式：
一行一个整数，表示至少要在几个城市中发布消息。
输入输出样例
输入样例#1：
5 4 1 2 2 1 2 3 5 1
输出样例#1：
2
说明
【数据范围】
对于20%的数据，n≤200;
对于40%的数据，n≤2,000;
对于100%的数据，n≤100,000，m≤500,000.
【限制】
时间限制：1s，内存限制：256M
【注释】
样例中在4,5号城市中发布消息。
tarjan求强联通分量，求出所有的强联通分量，缩点后数入度为0的（因为入度为0的点必须得知道消息，否则没有消息来源。）
1 #include<cstdio> 2 #include<algorithm> 3 #include<stack> 4 using namespace std; 5 6 const int MAXN = 100100; 7 struct Edge{ 8 int to,nxt; 9 }e[500100]; 10 int head[MAXN],dfn[MAXN],low[MAXN],bel[MAXN],t[MAXN],x[500100],y[500100]; 11 bool vis[MAXN]; 12 int cnt,n,m,tot,ans,num; 13 stack<int>s; 14 15 void add(int u,int v) 16 { 17 ++cnt; 18 e[cnt].to = v; 19 e[cnt].nxt = head[u]; 20 head[u] = cnt; 21 } 22 void tarjan(int u) 23 { 24 low[u] = dfn[u] = ++tot; 25 s.push(u); 26 vis[u] = true ; 27 for (int i=head[u]; i; i=e[i].nxt) 28 { 29 int v = e[i].to; 30 if (!dfn[v]) 31 { 32 tarjan(v); 33 low[u] = min(low[u],low[v]); 34 } 35 else if (vis[v]) low[u] = min(low[u],low[v]); 36 } 37 if (dfn[u]==low[u]) 38 { 39 int now = -1; 40 num++; 41 while (now!=u) 42 { 43 now = s.top(); 44 s.pop(); 45 bel[now] = num; 46 vis[now] = false ; 47 } 48 } 49 } 50 int main() 51 { 52 scanf("%d%d",&n,&m); 53 for (int i=1; i<=m; ++i) 54 { 55 scanf("%d%d",&x[i],&y[i]); 56 add(x[i],y[i]); 57 } 58 for (int i=1; i<=n; ++i) 59 if (!dfn[i]) tarjan(i); 60 for (int i=1; i<=m; ++i) 61 { 62 if (bel[x[i]]!=bel[y[i]]) 63 t[bel[y[i]]]++; 64 } 65 for (int i=1; i<=num; ++i) 66 if (t[i]==0) ans++; 67 printf("%d",ans); 68 return 0; 69 }