1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include<iostream>
#include<vector>
#include<cstring>
#define N 400010
using namespace std;
int i,j,n,m,lsum=1,dp,d,x,y,k,cnt;
int low[N],dfn[N],z[N],head[N],fa[N],v[N],f[N],bh[N],p[N];
int hash[N],ans[N];
struct {
int t,next;
}e[N*5];
inline void Add(int u,int t){
e[lsum].t=t; e[lsum].next=head[u]; head[u]=lsum++;
e[lsum].t=u; e[lsum].next=head[t]; head[t]=lsum++;
}
inline int find(int x){return (x==fa[x])?x:fa[x]=find(fa[x]);}
inline void Ready(){
int i=0,u=0,j=0,v=0;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=n;i++){
if (bh[i]) continue;
u=find(i); cnt++;
for (j=head[i];j;j=e[j].next){
if (bh[e[j].t]) continue;
v=find(e[j].t);
if (u!=v) {cnt--; fa[v]=u;}
}
}
}
inline void Work(){
int i=0,u=0,j=0,v=0;
scanf("%d",&k);
for (i=1;i<=k;i++) scanf("%d",&p[i]),p[i]++,bh[p[i]]=1;
Ready(); ans[k]=cnt;
for (i=k;i>=1;i--){
bh[p[i]]=0; u=find(p[i]); cnt++;
for (j=head[p[i]];j;j=e[j].next){
if (bh[e[j].t]) continue;
v=find(e[j].t);
if (u!=v) {cnt--; fa[v]=u;}
}
ans[i-1]=cnt;
}
for (i=0;i<=k;i++) printf("%dn",ans[i]);
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) {
scanf("%d%d",&x,&y); x++; y++;
Add(x,y);
}
Work();
return 0;
}
|
近期评论