题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入格式

输入文件第一行包含两个整数，$n,m$，分别表示星球的数目和以太隧道的数目。星球用 $0 \sim n-1$ 的整数编号。

接下来的 $m$ 行，每行包括两个整数 $x,y$，表示星球 $x$ 和星球 $y$ 之间有 “以太” 隧道，可以直接通讯。

接下来的一行为一个整数 $k$ ，表示将遭受攻击的星球的数目。

接下来的 $k$ 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 $k$ 个数互不相同，且都在 $0$ 到 $n-1$ 的范围内。

输出格式

第一行是开始时星球的连通块个数。接下来的 $k$ 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

输入样例

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

输出样例

1
1
1
2
3
3

【数据范围】

对于 $100\%$ 的数据，$1\le m \le 2\times 10^5$，$1\le n \le 2m$，$x \neq y$。

题解

离线+倒序加边

考虑一下这题，因为并没有过多的操作，只是要我们求一下连通块的个数而已（也就是连通性，具有传递性的连通），而这恰好是并查集所擅长的。

然而，我们正向看题目时就会发现支持删除操作的并查集似乎办不到。但如果我们把删除操作换成加入操作，就可以办到了。这也就是逆向思维。题目支持离线，所以我们可以逆向处理出所有答案以后再全部输出就好了。

1. 考虑最后的连通状态：标记摧毁的点，把不摧毁的点之间能连的边连起来，同时统计连通块的数量即为所求
2. 中间的连通状态：与最后的连通状态处理方法类似，从后往前依次加入被删除的点，枚举出边，统计连通块数。
3. 倒序存储，正序输出

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=4e5+10;
vector<int> g[N];
int p[N];
int a[N];
bool boom[N];
int ans[N];
int n,m,k;

inline int find(int x)
{
    if(p[x] != x)
        p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) p[i]=i;

    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    cin>>k;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&a[i]);
        boom[a[i]]=true;
    }

    for(int i=0;i<n;i++)
    {
        if(!boom[i])
        {
            for(int j=0;j<g[i].size();j++)
                if(!boom[g[i][j]])
                {
                    int pa=find(i);
                    int pb=find(g[i][j]);
                    p[pa]=pb;
                }
        }
    }

    int tot=0;
    for(int i=0;i<n;i++)
        if(p[i] == i && !boom[i])
            tot++;
    ans[k+1]=tot;

    for(int i=k;i>=1;i--)
    {
        boom[a[i]]=false;
        tot++;

        for(int j=0;j<g[a[i]].size();j++)
            if(!boom[g[a[i]][j]])
            {
                int pa=find(a[i]);
                int pb=find(g[a[i]][j]);
                if(pa != pb)
                {
                    p[pa]=pb;
                    tot--;
                }
            }
        ans[i]=tot;
    }
    for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
    // system("pause");
}