首页 > > 程序设计 > C/C++ >

P2002 消息扩散

2018-06-17 22:14:11来源：未知阅读 ()

题目背景

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

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据范围】

对于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 node
18 {
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])// root
55     {
56         colornum++;
57         int h;
58         do
59         {
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 }