并查集进阶版

过关代码如下

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;int n, m;
vector<int> edg[400005];
int a[400005], be[400005]; // a的作用就是存放要摧毁
int k;
int fa[400005];
int daan[400005];void add(int x, int y) {edg[x].push_back(y);edg[y].push_back(x);
}int find(int x) {if (x == fa[x]) return x;return fa[x] = find(fa[x]);
}void uni(int x, int y) {int xx = find(x), yy = find(y);if (xx == yy) return;fa[xx] = yy;
}int main() {cin >> n >> m;int l, r;for (int i = 1; i <= m; i++) {cin >> l >> r;add(l, r); // 建立边}cin >> k;for (int i = 1; i <= k; i++) {cin >> a[i];be[a[i]] = 1; // 标记为1，表示被摧毁}int ans = n-k; // 一开始的时候每个点都是一个块// 初始化并查集for (int i = 0; i <= n; i++) fa[i] = i;// 开始区分联通分量for (int i = 0; i < n; i++) {if (be[i]) continue;for (int u : edg[i]) {if (be[u]) continue;if (find(i) == find(u)) continue;uni(i, u);// 连接ans--;}}daan[k+1] = ans;for (int i = k; i >= 1; i--) {//cout << "yes" << endl;int xiufu = a[i];ans++;be[xiufu] = 0;  // 恢复为1for (int u : edg[xiufu]) {if (be[u]) continue;if (find(u) == find(xiufu)) continue;ans--;uni(u, xiufu);}daan[i] = ans;}for (int i = 1; i <= k+1; i++) {cout << daan[i] << endl;}//cout << " now";return 0;
}