Problem Description 题目链接
世界上存在着N个国家，简单起见，编号从0~N-1，假如a国和b国是盟国，b国和c国是盟国，那么a国和c国也是盟国。另外每个国家都有权宣布退盟（注意，退盟后还可以再结盟）。
定义下面两个操作：
“M X Y” ：X国和Y国结盟
“S X” ：X国宣布退盟
Input
多组case。
每组case输入一个N和M (1 ≤ N ≤ 100000 , 1 ≤ M ≤ 1000000),N是国家数，M是操作数。
接下来输入M行操作
当N=0，M=0时，结束输入
Output
对每组case输出最终有多少个联盟，格式见样例。
Sample Input
5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3
3 1
M 1 2
0 0
Sample Output
Case #1: 3
Case #2: 2
#include <iostream> #include <cstring> using namespace std; /* 思路:并查集的操作 涉及到并查集的删除 用俩个数组存储 使用虚根法，即每次指向根节点是未出现的过的，因此要保证数组开足够大 其中real[i]=p,表示节点i所存放的位置在father[p]，在father数组进行并查集的操作 这样可以保证当i节点删除的时候，不会影响原来的节点树结构 */ const int N = 300003; int real[N];//存放i节点的真正位置 int father[N];//用以并查集操作 int visit[N]; int t;//代表数组末尾未出现的点,用来删除操作存放 //寻找祖先 并使用路径压缩 可以缩短并查集的查找时间 int FindAncestor(int a) { if (father[a] == a) return a; return father[a] = FindAncestor(father[a]); } //并查集联合 void Union(int a, int b) { int an = FindAncestor(real[a]); int bn = FindAncestor(real[b]); if (an != bn) { //连a即可 father[bn] = an; } } //删除操作 void del(int x) { //指向一个新的未使用的位置，不会影响原先树结构 real[x] = t; father[t] = t++; } int main() { int N, M, ans = 1; while (scanf("%d%d", &N, &M), N || M) { t = N; for (int i = 0; i < N; i++) { real[i] = i; father[i] = i; } char a; int b, c; getchar(); while (M--) { scanf("%c", &a); if (a == 'M') { scanf("%d%d", &b, &c); Union(b, c); } else { scanf("%d", &b); del(b); } getchar(); } memset(visit, 0, sizeof(visit)); int res = 0; for (int i = 0; i < N; i++) { //查找根 若根未使用过 联盟数+1 int temp = FindAncestor(real[i]); if (!visit[temp]) { visit[temp] = 1; res++; } } printf("Case #%d: %d ", ans++, res); } return 0; }
参考链接：https://blog.csdn.net/a915800048/article/details/41703865