题目大意
给定编号从 0 到 N-1 的 N 个点，以及 M 条操作。有两种操作：
- M a b：合并 a 和 b 所在的集合（关系具有传递性）。
- S a：将点 a 从它当前所在的集合中删除，使其成为一个独立的孤立点。
最后需要输出整个操作结束后，一共有多少个不同的集合。
解题思路：虚拟节点法
这是一道经典的并查集变种问题——带删除操作的并查集。
难点在于：并查集并不支持直接删除一个节点，因为删除某个节点可能会影响其子节点的指向。
为了解决这个问题，这里引入“虚拟节点”（“虚父节点”）的技巧。
删除过程图解
图1: 无法删除 A节点
图2: 引入虚拟节点后，删除节点A的方法。
代码实现 (C++)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005; // 最大原始节点数
const int MAXM = 1000005; // 最大操作数
const int MAX_SIZE = MAXN + MAXN + MAXM; // 并查集数组总大小int n, m; // n:当前节点数, m:当前操作数
int Fa[MAX_SIZE]; // 并查集父节点数组
int flg[MAX_SIZE]; // 标记数组，用于最后统计集合个数int GetFa(int k) {if (k == Fa[k]) return k; // 自己是根，直接返回return Fa[k] = GetFa(Fa[k]); // 路径压缩：将父节点直接指向根
}
void Merge(int x, int y) {int fx = GetFa(x);int fy = GetFa(y);if (fx != fy) Fa[fx] = fy;
}int main() {for (int k = 1;; k++) {cin >> n >> m;if (n == 0 && m == 0) break;char ch; // 操作类型：M或Sint a, b; // 操作参数/*** 初始化阶段：* 为每个原始节点创建一个虚拟节点（马甲）* 原始节点编号：1 ~ n* 初始虚拟节点编号：n+1 ~ n+n* 预留空间：n+n+1 ~ n+n+m 用于删除操作*/// 步骤1：原始节点指向初始虚拟节点// 例如：Fa[1] = 1+n, Fa[2] = 2+n, ...for (int i = 1; i <= n; i++) Fa[i] = i + n;// 步骤2：初始化所有虚拟节点（包括初始虚拟节点和预留空间）// 虚拟节点指向自己，作为集合的根for (int i = n + 1; i <= n + n + m; i++) Fa[i] = i;int L = n + n; // 当前可用的新虚拟节点编号for (int i = 1; i <= m; i++) {scanf(" %c", &ch); if (ch == 'M') { // 合并操作scanf("%d%d", &a, &b);Merge(a + 1, b + 1);}if (ch == 'S') { // 删除操作cin >> a;L++; // 获取一个新的虚拟节点编号Fa[a + 1] = L; // 这样a就脱离了原来的集合，成为一个独立的点// 注意：虚拟节点L已经在初始化时指向自己，所以不需要额外设置}}memset(flg, 0, sizeof(flg)); int cnt = 0; for (int i = 1; i <= n; i++) {int x = GetFa(i);if (!flg[x]) cnt++ ,flg[x] = 1;}cout << "Case #" << k << ": " << cnt << endl;}return 0;
}