首页 > 代码库 > P2002 消息扩散
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号城市中发布消息。
先用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 消息扩散
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。