POJ 1988 Cube Stacking（并查集+路径压缩）

题目链接：

并查集的题目

【题目大意】

有n个元素，開始每一个元素自己 一栈。有两种操作，将含有元素x的栈放在含有y的栈的顶端，合并为一个栈。

另外一种操作是询问含有x元素以下有多少个元素。

用sum数组储存每一个栈中的元素个数。每次合并的时候将sum加到 父亲节点。也就是每一个栈的最底部。

用under数组储存当前节点以下有多少元素。每次合并的时候，就能够将顶端元素的under赋值为父节点也就是栈最底部的sum。

void Union(int x,int y){

	int xr = find(x);

	int yr = find(y);

	if(xr==yr) return;

	father[xr]=yr;

	under[xr]=sum[yr];

	sum[yr]+=sum[xr];

}

在查询的时候，运用递归的思想。从底部往上加under。

int find(int x){

	if(x==father[x])

		return father[x];

	int tmp = find(father[x]);

	under[x]+=under[father[x]]; //细致想想

	father[x]=tmp;

	return tmp;

}

【源码】

#include <iostream> //父亲节点在栈的底部

#include <cstdio>

using namespace std;

const int maxn = 30000+10;

int father[maxn];

int under[maxn];

int sum[maxn];

void init(){

	for(int i=0;i<maxn;i++){

		father[i]=i;

		under[i]=0;

		sum[i]=1;

	}

}

int find(int x){

	if(x==father[x])

		return father[x];

	int tmp = find(father[x]);

	under[x]+=under[father[x]];

	father[x]=tmp;

	return tmp;

}

void Union(int x,int y){

	int xr = find(x);

	int yr = find(y);

	if(xr==yr) return;

	father[xr]=yr;

	under[xr]=sum[yr];

	sum[yr]+=sum[xr];

}

int main(){

	int n;

	while(scanf("%d",&n)!=EOF){

		char ch;

		int a,b;

		init();

		for(int i=0;i<n;i++){

			scanf(" %c",&ch);

			if(ch=='M'){

				scanf("%d%d",&a,&b);

				Union(a,b);

			}

			else{

				scanf("%d",&a);

				int x=find(a); //仅仅是用来累加一下under

				printf("%d\n",under[a]);

			}

		}

	}

	return 0;

}