本场比赛第一题,给个简单的吧,这 100 分先拿着。
有n个城市,中间有单向道路连接,消息会沿着道路扩散,现在给出n个城市及其之间的道路,问至少需要在几个城市发布消息才能让这所有n个城市都得到消息。
输入格式:
第一行两个整数n,m表示n个城市,m条单向道路。
以下m行,每行两个整数b,e表示有一条从b到e的道路,道路可以重复或存在自环。
输出格式:
一行一个整数,表示至少要在几个城市中发布消息。
输入样例#1:
5 4
1 2
2 1
2 3
5 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 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 }