bzoj1015: [JSOI2008]星球大战starwar（并查集）

　　一眼题...倒着加点并查集判断是否连通即可，居然瞎写了个就1A了，美滋滋>v<

#include<bits/stdc++.h>
using namespace std;
const int maxn=500010,inf=1e9;
struct poi{int too,pre;}e[maxn];
int n,m,x,y,k,tot;
int damage[maxn],fa[maxn],last[maxn],ans[maxn];
bool v[maxn];
void read(int &k)
{
    int f=1;k=0;char c=getchar();
    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
    k*=f;
}
void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main()
{
    read(n);read(m);
    for(int i=1;i<=m;i++)
    {
        read(x);read(y);x++;y++;
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    read(k);
    for(int i=1;i<=k;i++)read(damage[i]),damage[i]++,v[damage[i]]=1;
    ans[k]=n-k;
    for(int i=1;i<=n;i++)
    if(!v[i])
    for(int j=last[i];j;j=e[j].pre)
    {
        if(v[e[j].too])continue;
        x=gf(i);y=gf(e[j].too);
        if(x!=y)fa[x]=y,ans[k]--;
    }
    for(int i=k;i;i--)
    {
        ans[i-1]=ans[i]+1;
        v[damage[i]]=0;
        for(int j=last[damage[i]];j;j=e[j].pre)
        {
            x=gf(damage[i]);
            y=gf(e[j].too);
            if(x!=y&&(!v[e[j].too]))ans[i-1]--,fa[x]=y;;
        }
    }
    for(int i=0;i<=k;i++)printf("%d
",ans[i]);
}