//564K 282MS C++
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct UF_Node{
int up;
int count;
int parent;
};
typedef struct UF_Node UF_Node;
UF_Node UF_Array[30001];
void creat(){
int c;
for(c = 0; c<=30000; c++){
UF_Array[c].count = 1;
UF_Array[c].parent = c;
UF_Array[c].up = 0;
}
}
int UF_find(int x) {
int xParent = UF_Array[x].parent;
if (xParent != x) {
UF_Array[x].parent = UF_find(xParent);
UF_Array[x].up += UF_Array[xParent].up;
}
return UF_Array[x].parent;
}
// a set top of b set
void UF_Union(int a, int b) {
int aroot = UF_find(a);
int broot = UF_find(b);
UF_Array[broot].up = UF_Array[aroot].count;
UF_Array[aroot].count += UF_Array[broot].count;
UF_Array[broot].parent = aroot;
}
int main(){
creat();
int n,a,b;
char s;
cin>>n;
while(n--){
cin>>s;
if(s == 'M'){
scanf("%d %d",&a,&b);
UF_Union(a,b);
}
else if(s == 'C'){
scanf("%d",&a);
b = UF_find(a);
printf("%d\n",UF_Array[b].count - UF_Array[a].up - 1);
}
}
return 0;
}
非常好的并查集的题, 看到这道题的时候,就感觉似乎可以跟集合 并查集扯上关系,但是因为自己的固定思维,觉得并查集只是用来判断是否一个集合之类的问题,这道题要求的是计数,觉得扯不上,后来搜了下,才发现并查集在加入一些扩展之后,也可以解这样的题,不由感叹数据结构真是博大精深,扩展一下就是一个新天地。
其实就是扩展了两个数据项: 一个是up 表示 此cube所属的集合(也就是stack)上面一共有多少个cube, 第二个是count,这个值只有在cube是stack的第一个元素(也就是集合的root)的时候才有效,代表着此集合(stack)所有的cube的数量,那么当要求某个cube X下面有多少个cube时,
在知道了此cube所属的stack(集合)有多少个cube: count,以及此cube上面有多少个cube: up, 此cube所属stack(集合)在X下面的cube数量就是 count - up - 1.
一些关键的操作就是:
<1> 在UF_Union(a, b), 即将a所属的stack加到 b所属的stack上时,除了更新常规的parent外,还要更新 aroot的count值,因为broot集合并入了aroot,那么aroot代表的集合的count就要加上 broot集合的数量, broot不用变化,因为broot已经不是 集合的root, 同时,因为broot上面有了cube,所以要将broot的up从 0 更新为 aroot集合的count,因为aroot集合的所有cube都在broot上面。
<2> 在UF_Find(a), 除了将a的parent更新为 aroot外,还有很关键的一点: a 的 up 要加上 其 parent(注意,这个parent是没有递归UF_find更新其parent之前的parent,可以理解为在一次合并以后, a的parent还没有更新,仍然指向原来集合的那个 parent,也就是 root), 因为 a原来的parent, 其up一定是0(因为在stack的最上面,因此上面没有cube), 那么在合并以后,其up就被更新aroot集合的count,这样,broot所属的stack,每个cube上面都多了 aroot的count,因此,在UF_find递归处理时,进行此操作,就等于将broot的每个cube都做了 +count的处理(递归一直是很巧妙的结构).