题目背景

本场比赛第一题，给个简单的吧，这 \(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\)号城市中发布消息。

思路：考虑tarjan，先缩点，然后看看有几个入度为0的点，即没有变连向这个点，那么就肯定要向这个城市发布消息，因为别的城市无法传给这个城市，所以答案就是缩点后入度为0的点的个数。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 100007using namespace std;int x,n,m,rd[maxn],head[maxn],dfn[maxn],low[maxn],js,num,cnt,bel[maxn];bool vis[maxn];inline int qread() {  char c=getchar();int num=0,f=1;  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;  for(;isdigit(c);c=getchar()) num=num*10+c-'0';  return num*f;}struct node {  int v,nxt;}e[500007];stack
        
         q;inline void ct(int u, int v) {  e[++num].v=v;  e[num].nxt=head[u];  head[u]=num;}void tarjan(int u) {  dfn[u]=low[u]=++cnt;  q.push(u),vis[u]=1;  for(int i=head[u];i;i=e[i].nxt) {    int v=e[i].v;    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);    else if(vis[v]) low[u]=min(low[u],dfn[v]);  }  if(dfn[u]==low[u]) {    int x;js++;    while(x!=u) {      x=q.top(),q.pop();      bel[x]=js,vis[x]=0;    }  }}int main() {  n=qread(),m=qread();  for(int i=1,u,v;i<=m;++i) {    u=qread(),v=qread();    ct(u,v);  }  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);  if(js==1) {printf("1\n");return 0;}  for(int u=1;u<=n;++u) {    for(int i=head[u];i;i=e[i].nxt) {      int v=e[i].v;      if(bel[v]!=bel[u]) rd[bel[v]]++;    }  }  for(int i=1;i<=js;++i) if(!rd[i]) x++;  printf("%d\n",x);  return 0;}