jsoi 2008スターウォーズbzoj 1015


//      ,                 0 n-1  WA   TLE        ,                     

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define N 400005
#define M 400005
using namespace std;
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
struct wakaka
{
        int x,y,next;
}e[M];
int ls[N],cnt,tot,f[N],used[N],v[N];
int ans[M],q[N],n,m,qes;

void add(int x,int y)
{
        cnt++;e[cnt].x=x;e[cnt].y=y;e[cnt].next=ls[x];ls[x]=cnt;
        cnt++;e[cnt].x=y;e[cnt].y=x;e[cnt].next=ls[y];ls[y]=cnt;
}

int findd(int x)
{
        if (f[x]==x) return x;
        int k=findd(f[x]);
        f[x]=k;return k;
}

void ins(int x)
{
        int p=findd(x);
        for (int i=ls[x];i!=0;i=e[i].next)
        {
                if (used[e[i].y])
                {
                        int q=findd(e[i].y);
                        if (p!=q)
                        {
                                f[q]=p;
                                tot--;
                        }
                }
        }
}

int main()
{
        memset(v,0,sizeof(v));
        memset(used,0,sizeof(used));
        n=read();m=read();
        for (int i=0;i<n;i++)f[i]=i;
        for (int i=1;i<=m;i++)
        {
                int x=read(),y=read();
                add(x,y);
        }
        qes=read();
        for (int i=1;i<=qes;i++)
        {
                int x=read();
                v[x]=1;
                q[i]=x;
        }
        for (int i=0;i<n;i++)
                if (v[i]==0)
        {
                tot++;
                ins(i);
                used[i]=1;
        }
        ans[qes+1]=tot;
        for (int i=qes;i>=1;i--)
        {
                tot++;
                ins(q[i]);
                used[q[i]]=1;
                ans[i]=tot;
        }
        for (int i=1;i<=qes+1;i++)
                printf("%d
",ans[i]); return 0; }