游客 注册 | 登录
中文 | En

3048 - 破坏

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

      农夫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接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚. 

题目输入

  • 第1行: 三个空格分开的数: P, C, 和 N 
  • 第2..C+1行: 每行两个空格分开的数: a_i 和 b_i 
  • 第C+2..C+N+1行: 每行一个数: report_j 

题目输出

  • 第1行: 一个数,最少不能回到农庄的牛的数目(包括损坏的牛棚). 

输入/输出样例

输入格式

4 3 1
1 2
2 3
3 4
3

输出格式

3

C++解答

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#define s1 100002
#define s2 200002
#define s3 30005
using namespace std;
struct  node
{
	int y;
	int next;
}e[s2];
int tot=0;
int g[s3]={0};
bool b[s3]={0};

void jian(int x,int y)
{
	e[++tot].y=y;
	e[tot].next=g[x];
	g[x]=tot;
}

int main()
{
	//freopen("damage.in","r",stdin);
	//freopen("damage.out","w",stdout);
	int n,p,c;
    cin>>p>>c>>n;
    
    int x,y,m;
    queue <int> q;
   
	for(int i=1;i<=c;i++)
	{
		cin>>x>>y;
		jian(x,y);
		jian(y,x);
	}
	
	for(int i=1;i<=n;i++)
	{
		cin>>m;
		q.push(m); 
		b[m]=1;
		int pos=g[m];
		while(pos!=0)
		{
			b[e[pos].y]=1;	
			pos=e[pos].next;
		}	
		
   }
		
	q.push(1);
	b[1]=1;
	int sum=1;
	while(!q.empty())
	{
		    int f=q.front();
			int pos=g[f];
			while(pos!=0)
			{
				if(!b[e[pos].y])
				{
					q.push(e[pos].y);
					b[e[pos].y]=1;
		            sum++;
				}
				pos=e[pos].next;
			}
			q.pop();
	}
	cout<<p-sum;
	return 0;
}
请先登陆