[文章目录]
Description
农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用. FJ的农场有P(1 <= P <= 30,000)个牛棚,编号1..P. C(1 <= C <= 100,000)条双向路经联接这些牛棚,编号为1..C. 路经i连接牛棚a_i和b_i (1 <= a_i<= P;1 <= b_i <= P).路经可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚. N (1 <= N <= P)头在不同牛棚的牛通过手机短信report_j(2 <= report_j <= P)告诉FJ它们的牛棚(report_j)没有损坏,但是它们无法通过路经和没有损坏的牛棚回到到农场. 当FJ接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚
贪心，如果一个点不可达，那么其周围的点要么不可达，要么损坏。既然要求最少的数目，直接损坏周围的点肯定是最优解（否则也不可达）。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,c,p,ans;
int head[31000],to[201000],nxt[201000],cnt;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
queue<int>q;
bool vis[31000],v[31000];
void bfs()
{
vis[1]=1; q.push(1);
while(!q.empty())
{
ans++;
int x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(!v[to[i]]&&!vis[to[i]])
vis[to[i]]=1,q.push(to[i]);
}
}
int main()
{
scanf("%d%d%d",&p,&c,&n);
int x,y;
for(int i=1;i<=c;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
while(n--)
{
scanf("%d",&x);
v[x]=1;
for(int j=head[x];j;j=nxt[j])
v[to[j]]=1;
}
bfs();
printf("%d\n",p-ans);
return 0;
}