合纵连横
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
乱世天下，诸侯割据。每个诸侯王都有一片自己的领土。但是不是所有的诸侯王都是安分守己的，实力强大的诸侯国会设法吞并那些实力弱的，让自己的领土面积不断扩大。而实力弱的诸侯王为了不让自己的领土被吞并，他会联合一些其他同样弱小的诸侯国，组成联盟(联盟不止一个)，来共同抵抗那些强大的诸侯国。 强大的诸侯国为了瓦解这些联盟，派出了最优秀的间谍来离间他们，使一些诸侯国退出联盟。最开始，每个诸侯国是一个联盟。
有两种操作
1、U x y 表示x和y在同一个联盟。（0≤x，y<n）
2、D x 表示x退出联盟。
- 输入
- 多组测试数据
第一行两个数，n和m（1 ≤ n≤ 10^5, 1 ≤ m ≤10^5），分别表示诸侯国的个数和操作次数。
接下来有m行操作 - 输出
- 输出联盟的个数
- 样例输入
5 7
U 0 1
U 1 2
U 0 3
D 0
U 1 4
D 2
U 0 2
10 1
U 0 9- 样例输出
Case #1: 2
Case #2: 9/**
分析：主要考察并查集中点的删除
算法：
Ⅰ、以前并查集是以其 1 - n 中的元素即作根节点又作子节点
《这样删除 pre [a] = n ++; 的话会使原先在一个区域的点可能不在一个区域了》
Ⅱ、现在我们将所有 1 - n 中的点作为子节点，n - 2n 的点作为根节点
《这样我们删除 pre [a] = 2n ++;的时候就不会打乱以前已在一个区域的点》
Ⅲ、其中 my_find()、my_join() 与以前并查集模板一致 关键代码：
void init () {
for (int i = 0; i < n; ++ i)
pre [i] = i + n;
for (int i = n; i < 2*n + m; ++ i)
pre [i] = i;
pos = 2*n;
return ;
]
**/C/C++代码实现（AC）：
#include <bits/stdc++.h> using namespace std; int n, m, pre [], pos; void init () {
for (int i = ; i < n; ++ i)
pre [i] = i + n;
for (int i = n; i < n + n + m; ++ i)
pre [i] = i;
pos = n + n;
return ;
} int my_find (int x) {
int n1 = x;
while (n1 != pre [n1]) {
n1 = pre [n1];
}
int i = x, j;
while (pre [i] != n1) {
j = pre [i];
pre [i] = n1;
i = j;
}
return n1;
} void my_join (int a, int b) {
int n1 = my_find (a), n2 = my_find (b);
if (n1 != n2)
pre [n1] = n2;
} int main () {
int k = ;
while (~scanf ("%d%d", &n, &m)) {
init ();
char c;
int a, b, ans = , temp [] = {};
for (int i = ; i < m; ++ i) {
getchar ();
scanf ("%c", &c);
if (c == 'U') {
scanf ("%d%d", &a, &b);
my_join (a, b);
}
else {
scanf ("%d", &a);
pre [a] = pos ++;
}
} for (int i = ; i < n; ++ i) { // 查找有多少个区域
if (!temp [my_find (i)]) { // 在一个区域的有共同的根节点
temp [my_find (i)] = ;
++ ans;
}
}
printf ("Case #%d: %d\n", k ++, ans);
}
}