【并查集】poj 1988 Cube Stacking

题目描述：

http://poj.org/problem?id=1988

 

中文大意：

N 个堆栈，每个堆栈可以存放多个数据。有两种操作：移动和计数。

①移动：将包含数据 x 的堆栈移动到包含数据 y 的堆栈的顶部。

②计数：统计数据 x 下方的数据个数。

 

思路：

一个堆栈就是一个集合。

x 下方的节点个数 = x 所在集合的节点个数 - x 到根节点的距离 - 1

本题的难点在于，如何更新每个节点到根节点的距离。

在合并操作中，dis[y] = cnt[x]; 只是改变了原根节点到新根节点的距离，而非根节点到新根节点的距离并未改变。

非根节点到新根节点的距离 = 当前节点到原根节点的距离 + 原根节点到新根节点的距离 + ... 

非根节点到新根节点的距离，需要利用迭代操作来计算，请结合下面例子自行体会：

4

M 1 2

M 3 1

M 4 3

C 3

代码：

#include<iostream>
using namespace std;

int cnt[30001];//各集合的节点数 
int sets[30001];//各节点的所属集 
int dis[30001];//各节点到根节点的距离 

//初始化，每个节点属于独立的集合 
void init(){
    for(int i=1;i<=30000;i++){
        cnt[i] = 1;
        sets[i] = i;
        dis[i] = 0;
    }
}

//寻找节点 x 的所属集 
int find(int x){
    if(sets[x] == x){
        return x;
    } 
    int root = find(sets[x]);
    //当前节点到根节点的距离 = 当前节点到原根节点的距离 + 原根节点到新根节点的距离 
    dis[x] = dis[x] + dis[sets[x]];
    sets[x] = root;
    return root;
}

void union_set(int x, int y){
    x = find(x);
    y = find(y);
    
    //y 的所在集合并到 x 的所在集 
    sets[y] = x; 
    dis[y] = cnt[x];
    cnt[x] += cnt[y];
}

int main(){
    init();
    int p;
    scanf("%d", &p);
    
    char opt;
    int x,y;
    for(int i=0;i<p;i++){
        getchar();
        scanf("%c", &opt);
        
        if(opt == 'M'){
            scanf("%d %d", &x, &y);
            union_set(x, y);
        }
        else if(opt == 'C'){
            scanf("%d", &x);
            int root = find(x);
            int result = cnt[root] - dis[x] - 1;
            printf("%d
", result); 
        }
    }
}