并查集进阶版

过关代码如下

1. #define _CRT_SECURE_NO_WARNINGS
2. #include<bits/stdc++.h>
3. #include<unordered_set>
4. using namespace std;
6. int n, m;
7. vector<int> edg[400005];
8. int a[400005], be[400005]; // a的作用就是存放要摧毁
9. int k;
10. int fa[400005];
11. int daan[400005];
13. void add(int x, int y) {
14.         edg[x].push_back(y);
15.         edg[y].push_back(x);
16. }
18. int find(int x) {
19.         if (x == fa[x]) return x;
20.         return fa[x] = find(fa[x]);
21. }
23. void uni(int x, int y) {
24.         int xx = find(x), yy = find(y);
25.         if (xx == yy) return;
26.         fa[xx] = yy;
27. }
29. int main() {
30.         cin >> n >> m;
31.         int l, r;
32.         for (int i = 1; i <= m; i++) {
33.                 cin >> l >> r;
34.                 add(l, r); // 建立边
35.         }
36.         cin >> k;
37.         for (int i = 1; i <= k; i++) {
38.                 cin >> a[i];
39.                 be[a[i]] = 1; // 标记为1，表示被摧毁
40.         }
41.         int ans = n-k; // 一开始的时候每个点都是一个块
42.         // 初始化并查集
43.         for (int i = 0; i <= n; i++) fa[i] = i;
44.         // 开始区分联通分量
45.         for (int i = 0; i < n; i++) {
46.                 if (be[i]) continue;
47.                 for (int u : edg[i]) {
48.                         if (be[u]) continue;
49.                         if (find(i) == find(u)) continue;
50.                         uni(i, u);// 连接
51.                         ans--;
52.                 }
53.         }
54.         daan[k+1] = ans;
55.         for (int i = k; i >= 1; i--) {
56.                 //cout << "yes" << endl;
57.                 int xiufu = a[i];
58.                 ans++;
59.                 be[xiufu] = 0;  // 恢复为1
60.                 for (int u : edg[xiufu]) {
61.                         if (be[u]) continue;
62.                         if (find(u) == find(xiufu)) continue;
63.                         ans--;
64.                         uni(u, xiufu);
65.                 }
66.                 daan[i] = ans;
67.         }
68.         for (int i = 1; i <= k+1; i++) {
69.                 cout << daan[i] << endl;
70.         }
71.         //cout << " now";
72.         return 0;
73. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。