【BZOJ】1015 星球大战

【解析】排序+并查集

[分析]
求联通块，每操作一次询问一次。
搜索？ O(N^2)，TLE。
并查集，根据上次的结果更新答案。
问题在于，这是分离的操作，而不是合并的，怎么办呢？
反过来不就是合并的了吗？

给每个点标号，表示它打击的先后次序，例如结点3是第2个打击的，level[3]=2。
对于所有未打击的点，标号为打击的个数nl+1。
然后对于每条边，它一定是在第edge[i].w=min(level[edge[i].u]],level[edge[i].v])次打击不存在的。
根据w值从大到小排序。

然后动态维护res，反过来搞。
初始时res=n-nl，然后每次操作由于多了一个点，res++，然后考虑这个节点连通的情况，如果有连通则res--。
最后反过来输出答案。

[小结]
①对于每次操作求连通块个数的问题，通常采用并查集。
②对于动态分离，合并的问题，通常采用并查集。
③并查集的两个作用：合并，查找。

[代码]

/**************************************************************
    Problem: 1015
    User: y20070316
    Language: C++
    Result: Accepted
    Time:912 ms
    Memory:7840 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
 
const int N=400001;
const int M=200001;
 
struct E
{
    int u,v,w;
}edge[M];
int n,m;
int f[N],res[N];
int level[N],nl;
 
inline int read(void)
{
    int s=0,t=1; char c=getchar();
    for (;c<'0'||c>'9';c=getchar()) if (c=='-') t=-1;
    for (;'0'<=c&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*t;
}
 
inline int min(int i,int j)
{
    return i<j?i:j;
}
 
inline int cmp(E ea,E eb)
{
    return ea.w>eb.w;
}
 
int find(int i)
{
    return f[i]==i?i:f[i]=find(f[i]);
}
 
int main(void)
{   
    int x;
    n=read(),m=read();
    for (int i=1;i<=m;i++) 
    {
        edge[i].u=read(); edge[i].u++;
        edge[i].v=read(); edge[i].v++;
    }
    nl=read();
    for (int i=1;i<=nl;i++) x=read(),level[++x]=i;
    for (int i=1;i<=n;i++)
        if (!level[i]) level[i]=nl+1;
     
    for (int i=1;i<=m;i++)
        edge[i].w=min(level[edge[i].u],level[edge[i].v]);
    sort(edge+1,edge+m+1,cmp);
     
    int j=0,fu,fv;
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=nl+1;i;i--)
    {
        res[i]=(i==nl+1?n-nl:res[i+1]+1);
        for (;j<m&&edge[j+1].w==i;)
        {
            fu=find(edge[++j].u);
            fv=find(edge[j].v);
            if (fu^fv) f[fu]=fv,res[i]--;
        }
    }
    for (int i=1;i<=nl+1;i++) printf("%d\n",res[i]);
     
    return 0;
}