P1197 [JSOI2008]星球大战

https://www.luogu.org/problem/show?pid=1197

思路和关闭农场差不多，不过加了一些时间上的优化。
当我们加入一个点时，先假设又加入一个单独的连通块，然后再扫一下与它相连的点如果在图中但是与它不在一个联通块中，那么就将其合并，连通块个数减一。
注：并查集的题果断找祖宗。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#define N 400000
using namespace std;
int n,m,k,tot;
int head[N+100],nxt[N+100],num[N+100],cnt;
int Q[N+100],f[N+100],ans[N+100];
bool f1[N+5];
void add(int x,int y)
{
    num[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
} 
void connect(int x)
{
    tot++;
    for(int i=head[x];i;i=nxt[i])
     if(f1[num[i]]){
        int fa=find(x),fb=find(num[i]);
        if(fa!=fb)
        {
            f[fb]=fa;
            tot--;
        }   
    }
    f1[x]=1;    
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) f[i]=i,f1[i]=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++) scanf("%d",&Q[i]),f1[Q[i]]=0;
    for(int i=0;i<n;i++) if(f1[i]) connect(i);

    for(int i=k;i>=0;i--)
    {
        ans[i+1]=tot;

        if(i==0) break;

        connect(Q[i]);
    }
    for(int i=1;i<=k+1;i++)
     printf("%d
",ans[i]);
    return 0;
}