题目背景

本场比赛第一题，给个简单的吧，这 100 分先拿着。

题目描述

有n个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出n个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有n个城市都得到消息。

输入输出格式

输入格式：

 

第一行两个整数n,m表示n个城市，m条单向道路。

以下m行，每行两个整数b,e表示有一条从b到e的道路，道路可以重复或存在自环。

 

输出格式：

 

一行一个整数，表示至少要在几个城市中发布消息。

 

输入输出样例

输入样例#1：

5 41 22 12 35 1

输出样例#1：

2

说明

【数据范围】

对于20%的数据，n≤200;

对于40%的数据，n≤2,000;

对于100%的数据，n≤100,000，m≤500,000.

【限制】

时间限制：1s，内存限制：256M

【注释】

样例中在4,5号城市中发布消息。

分析：首先想到的肯定是要缩点，但是答案并不是缩点后的点数，而是入度为0的强连通分量，我们只需要枚举每个点和这个点的边指向的点，如果不在同一个强连通分量里，则后一个点的强连通分量的入度++.

注意i和scc[i]不要弄混了，有时候写着写着就把点和缩后的点弄混了.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn = 100010,maxm = 500010;int n,m,head[maxn],to[maxm],nextt[maxm],tot = 1,pre[maxn],low[maxn],dfs_clock,scc[maxn],cnt,ans,rudu[maxn]; stack
           
             s;void add(int x,int y){ to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void tarjan(int u){ pre[u] = low[u] = ++dfs_clock; s.push(u); for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (!pre[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if (!scc[v]) low[u] = min(low[u],pre[v]); } if (low[u] == pre[u]) { ++cnt; while (1) { int t = s.top(); s.pop(); scc[t] = cnt; if (t == u) break; } }}int main(){ scanf("%d%d",&n,&m); for (int i = 1; i <= m; i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); } for (int i = 1; i <= n; i++) if (!scc[i]) tarjan(i); for (int i = 1; i <= n; i++) for (int j = head[i]; j;j = nextt[j]) { int v = to[j]; if (scc[i] != scc[v]) rudu[v]++; } for (int i = 1; i <= cnt; i++) if (!rudu[i]) ans++; printf("%d\n",ans); return 0;}