首页 > 代码库 > P2002 消息扩散
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的（因为入度为0的点必须得知道消息，否则没有消息来源。）
1 #include<cstdio> 2 #include<algorithm> 3 #include<stack> 4 using namespace std; 5 6 const int MAXN = 100100; 7 struct Edge{ 8 int to,nxt; 9 }e[500100];10 int head[MAXN],dfn[MAXN],low[MAXN],bel[MAXN],t[MAXN],x[500100],y[500100];11 bool vis[MAXN];12 int cnt,n,m,tot,ans,num;13 stack<int>s;14 15 void add(int u,int v)16 {17 ++cnt;18 e[cnt].to = v;19 e[cnt].nxt = head[u];20 head[u] = cnt;21 }22 void tarjan(int u)23 {24 low[u] = dfn[u] = ++tot;25 s.push(u);26 vis[u] = true ;27 for (int i=head[u]; i; i=e[i].nxt)28 {29 int v = e[i].to;30 if (!dfn[v])31 {32 tarjan(v);33 low[u] = min(low[u],low[v]);34 }35 else if (vis[v]) low[u] = min(low[u],low[v]);36 }37 if (dfn[u]==low[u])38 {39 int now = -1;40 num++;41 while (now!=u)42 {43 now = s.top();44 s.pop();45 bel[now] = num;46 vis[now] = false ;47 }48 }49 }50 int main()51 {52 scanf("%d%d",&n,&m);53 for (int i=1; i<=m; ++i)54 {55 scanf("%d%d",&x[i],&y[i]);56 add(x[i],y[i]);57 }58 for (int i=1; i<=n; ++i)59 if (!dfn[i]) tarjan(i);60 for (int i=1; i<=m; ++i)61 {62 if (bel[x[i]]!=bel[y[i]])63 t[bel[y[i]]]++;64 }65 for (int i=1; i<=num; ++i)66 if (t[i]==0) ans++;67 printf("%d",ans);68 return 0;69 }
P2002 消息扩散
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。