算法高级部分--并查集：方块栈（POJ1988）

1.题源：

POJ1988

2.题目描述

贝西正在玩游戏，方块编号为1～N（1<= N <= 1000）, 开始时每个方块都相当于一个栈。贝西执行一系列操作， 操作类型有两种： MXY，将包含X的栈整体移动到包含Y的栈顶部； C X，查询X方块下的方块数量。 请统计贝西每个查询操作的结果。

输入： 第一行为单个整数N， 表示方块的数量。 第2 行开始每行进行一个操作。

输入样例：
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出样例：
1
0
2

3.思路

法一：静态链表，直接暴力(超时了)

1. 结构体定义以及和初始化

struct node{
	int head;
	int next;
};

for(int i=1;i<=n;i++){
	 box[i].head=i;
	 box[i].next=-1;
}
1
2
3
4
5
6
7
8
9

2.合并操作

void move(int x,int y){
	int p=x;
	while(box[p].next!=-1){
		p=box[x].next;
	}
	box[p].next=box[y].head;
	box[y].head=box[p].head;
} 
1
2
3
4
5
6
7
8

3.查询操作

int find(int x){
	int count=0,p=x;
	while(box[p].next!=-1){
		count++;
		p=box[p].next;
	}
	return count;
}
1
2
3
4
5
6
7
8

法二：并查集
1.初始化

void Init(){
	for(int i=1;i<=30000;i++){
	fa[i]=i;
	d[i]=0;//第i个节点下的方块数量为0
	cnt[i]=1;//第i个栈的方块数量为1
	}
}

1
2
3
4
5
6
7
8

2.查询

int Find(int x){

}
1
2
3

3.合并

void Union(int x,int y){
	int a=Find(x);
	int b=Find(y);
	fa[a]=b;
	d[a]=cnt[b];
	cnt[b]+=cnt[a];
}
1
2
3
4
5
6
7

3.全部代码

#include 
using namespace std;
int fa[30001]={0};
int d[30001]={0};
int cnt[30001]={0};
void Init(){
	for(int i=1;i<=30000;i++){
	fa[i]=i;
	d[i]=0;//第i个节点下的方块数量为0
	cnt[i]=1;//第i个栈的方块数量为1
	}
}
int find(int x){
	//
	int fx=fa[x];
	if(x!=fa[x]){
		fa[x]=find(fa[x]);
		d[x]+=d[fx]; 
	}
	return fa[x];
}

void Union(int x,int y){
	int a=find(x);
	int b=find(y);
	if(a!=b){
		fa[a]=b;
		d[a]=cnt[b];
		cnt[b]+=cnt[a];	
	}	
}
int main(){
	Init();
	int n;
	 while(scanf("%d",&n)==1&&n)
    {
		for(int i=1;i<=n;i++){
			char c;
			cin>>c;
			int x,y;
			if(c=='M'){
				cin>>x>>y;
				Union(x,y);
			} 
			if(c=='C'){
				cin>>x;
				find(x);
                cout<<d[x]<<endl;
			} 
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52