3048 - 破坏
农夫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接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚.
Input
- 第1行: 三个空格分开的数: P, C, 和 N
- 第2..C+1行: 每行两个空格分开的数: a_i 和 b_i
- 第C+2..C+N+1行: 每行一个数: report_j
Output
- 第1行: 一个数,最少不能回到农庄的牛的数目(包括损坏的牛棚).
Examples
Input
4 3 1 1 2 2 3 3 4 3
Output
3
Hint
输出解释:
牛棚2遭到损坏,导致牛棚2, 3, 4里面的牛无法回到农庄.
Solution 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; }
Hint
输出解释:
牛棚2遭到损坏,导致牛棚2, 3, 4里面的牛无法回到农庄.