首页 > 代码库 > P2002 消息扩散

P2002 消息扩散

2024-10-22 06:30:39   211人阅读

题目背景

本场比赛第一题，给个简单的吧，这 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的点

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 using namespace std; 9 const int MAXN=500001;10 static void read(int &n)11 {12     char c=‘+‘;int x=0;bool flag=0;13     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}14     while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c-48);c=getchar();}15     flag==1?n=-x:n=x;16 }17 struct node18 {19     int u,v,nxt;20 }edge[MAXN];21 int head[MAXN];22 int num=1;23 void add_edge(int x,int y)24 {25     edge[num].u=x;26     edge[num].v=y;27     edge[num].nxt=head[x];28     head[x]=num++;29 }30 int dfn[MAXN];31 int low[MAXN];32 int tot=0;33 bool vis[MAXN];34 int color[MAXN];35 int colornum;36 stack<int>s;37 void tarjan(int now)38 {39     dfn[now]=low[now]=++tot;40     vis[now]=1;41     s.push(now);42     for(int i=head[now];i!=-1;i=edge[i].nxt)43     {44         if(!dfn[edge[i].v])45         {46             tarjan(edge[i].v);47             low[now]=min(low[now],low[edge[i].v]);48         }49         else if(vis[edge[i].v])// 公共祖先 50         {51             low[edge[i].u]=min(low[edge[i].u],dfn[edge[i].v]);52         }53     }54     if(dfn[now]==low[now])// root55     {56         colornum++;57         int h;58         do59         {60             h=s.top();61             if(!color[s.top()])62             color[s.top()]=colornum;63             vis[s.top()]=0;64             s.pop();65         }while(now!=h);66     }67 }68 int main()69 {70     int n,m;71     memset(head,-1,sizeof(head));72     read(n);read(m);73     for(int i=1;i<=m;i++)74     {75         int x,y;76         read(x);read(y);77         add_edge(x,y);78     }79     80     for(int i=1;i<=n;i++)81         if(!dfn[i])82             tarjan(i);83     memset(vis,0,sizeof(vis));84     for(int i=1;i<=n;i++)85         for(int j=head[i];j!=-1;j=edge[j].nxt)86             if(color[i]!=color[edge[j].v])87                 vis[color[edge[j].v]]=1;// 统计入度为0的点 88     int ans=0;89     for(int i=1;i<=colornum;i++)90         if(!vis[i])91             ans++;92     printf("%d",ans);93     return 0;94 }

 

P2002 消息扩散


联系
我们