P2002 消息扩散

题目背景

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

 

强连通分量裸题

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 5200000using namespace std;bool vis[N];int n,m,x,y,top,tim,tot,sum,ans,ans1,ans2;int in[N],out[N],dfn[N],low[N],head[N],stack[N],belong[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f; }struct Edge{    int from,to,next;}edge[N];int add(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;}int tarjan(int now){    dfn[now]=low[now]=++tim;    stack[++top]=now;vis[now]=true;    for(int i=head[now];i;i=edge[i].next)    {        int t=edge[i].to;        if(vis[t]) low[now]=min(low[now],dfn[t]);        else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]);    }    if(dfn[now]==low[now])    {        sum++;belong[now]=sum;        for(;stack[top]!=now;top--)         belong[stack[top]]=sum,vis[stack[top]]=false;        vis[now]=false; top--;    }}int shink_point(){    for(int i=1;i<=n;i++)     for(int j=head[i];j;j=edge[j].next)      if(belong[i]!=belong[edge[j].to])       in[belong[edge[j].to]]++;}int main(){    n=read(),m=read();    for(int i=1;i<=m;i++)     x=read(),y=read(),add(x,y);    for(int i=1;i<=n;i++)     if(!dfn[i]) tarjan(i);    shink_point();    for(int i=1;i<=sum;i++)     if(!in[i]) ans++;    printf("%d",ans);    return 0;}