poj 1988 Cube Stacking

点击打开链接poj 988

思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面，C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素，那么对于指令M x y我们始终把左边的合并到右边，那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样，它是把x所在的集合放在y所在集合上面，实际上是x的跟节点合并到y集合的最远点，所以我们应该开个数组记录当前集合最远的点

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 300010;

int father[MAXN];
int rank[MAXN];
int max_rank[MAXN];

void init(int n){
    memset(rank , 0 , sizeof(rank));
    memset(max_rank , 0 , sizeof(max_rank));
    for(int i = 1 ; i <= n ; i++)
        father[i] = i;
}

int find(int x){
    if(father[x] != x){
       int fa = father[x];
       father[x] = find(fa);
       rank[x] += rank[fa];
    }
    return father[x];
}

void move(int x , int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy){
        father[fx] = fy;
        rank[fx] = max_rank[fy]+1;
        max_rank[fy] += max_rank[fx]+1;
    }
}

int main(){
    char ch;
    int n , x , y;
    while(scanf("%d%*c" , &n) != EOF){
         init(n);
         for(int i = 0 ; i < n ; i++){
            scanf("%c" , &ch);
            if(ch == 'M'){
               scanf("%d%d%*c" , &x , &y);
               move(x , y);
            }
            else{
               scanf("%d%*c" , &x);
               int fx = find(x);// 注意先压缩
               printf("%d\n" , rank[x]);
            }
         }
    }
    return 0;
}