[JSOI2008]星球大战并查集

这一阵子因为好多原因，学习时间有点少，还好时间不算很长。
这两天写了道并查集的题目，感觉不错。
题目描述

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

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

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

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

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

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

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

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

第一行是开始时星球的连通块个数。接下来的 kkk 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。
输入输出样例
输入：

输出：

题解：
一开始也是没有思路，究竟怎么断开？？？
好吧，是我愚钝了，看了大牛们的题解以后，原来可以倒着做。。。

倒着做的思路就是，在并查集的过程中，把所有被摧毁的星球都不给他加到集合里去。这样连完之后就是最后一种情况。然后我们倒着给他一条一条的修复，答案存起来，最后输出即可。

我们先把所有的便给储存起来，然后再用邻接表把各个点所连的边给存起来
这个时候我们还没有开始并查集操作。

进行并查集操作，注意被摧毁的星球都不连。

找一共有几个集合。

开始给他修复，顺便存答案即可。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;

vector<pair<int,int> > v;  //储存所有边
vector<int> a;   //储存坏点
vector<vector<int> > edge;  //建图
bool pp[maxn];  //标记当前星球是否呗摧毁
int f[maxn];   //并查集数组
int n,m;
bool rem[maxn];   
int ans[maxn],cnt;
void init(){
    for(int i=0;i<n;i++) f[i]=i;
    memset(rem,false,sizeof rem);
    memset(pp,false,sizeof pp);
    edge.resize(maxn);
}
int ifind(int x){
    if(f[x]==x) return x;
    else return f[x]=ifind(f[x]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
        v.push_back(make_pair(x,y));
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x;
        cin>>x;
        a.push_back(x);
        pp[x]=true;
    }
    for(auto i:v){
        if(!pp[i.first]&&!pp[i.second]){
            int dx=ifind(i.first);
            int dy=ifind(i.second);
            if(dx!=dy){
                f[dx]=dy;
            }
        }
    }

    for(int i=0;i<n;i++){
        int dx=ifind(i);
        rem[dx]=true;
    }
    for(int i=0;i<n;i++){
        if(rem[i]&&!pp[i]) cnt++;
    }
    //cout<<cnt<<endl;
    for(int i=k-1;i>=0;i--){
        int u=a[i];
        ans[i]=cnt;
        cnt++;
        pp[u]=false; //修复
        for(int j=0;j<edge[u].size();j++){
            int v=edge[u][j];
            int dx=ifind(u);
            int dy=ifind(v);
            if(dx!=dy&&!pp[v]){
                f[dx]=dy;
                cnt--;
            }
        }
    }
    cout<<cnt<<endl;
    for(int i=0;i<k;i++){
        cout<<ans[i]<<endl;
    }
    return 0;

}

[JSOI2008]星球大战 并查集

[JSOI2008]星球大战并查集