poj 1988 Cube Stacking（并查集）

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## poj 1988 Cube Stacking（并查集）

Cube Stacking
 Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 14901 Accepted: 5037 Case Time Limit: 1000MS

Description

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input file.

Sample Input

```6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
```

Sample Output

```1
0
2
```

Source

```/*
* 方法一，超时，这里用了一个lower 来表示找下一个立方块，
* 这里使用的是循环，所以么每次都会把下方的cube遍历一遍，造成超时
*/

#include <iostream>
#include <stdio.h>
#define MAXNUM 30001
using namespace std;

typedef struct
{
int count;//记录改立方体下方所有的立方体个数
int parent;//指向立方体所在堆最上边的那个立方体
int lower;//指向当前立方体的下方那个块
}Cube;
Cube cube[MAXNUM];

void init()
{
for(int i = 1;i < MAXNUM; i++)
{
cube[i].count = 0;//初始化每个立方体下方均为0
cube[i].parent = i;//初始化每个立方体为单个堆，并且为当前堆最上边
cube[i].lower = 0;
}
}

//合并x,y所在的堆
void union_set(int x,int y)
{
int lower_parent;//下方堆中格子的最父节点
int lower_cube;//下方格子下标
int parent;//上方堆的最父节点下标

parent = cube[x].parent;
lower_parent = cube[y].parent;
lower_cube = x;
//更新上方的stack，在当前的cube下所有的count都要变化
while(cube[lower_cube].lower!=0)
{
cube[lower_cube].count = cube[lower_parent].count+1;
lower_cube = cube[lower_cube].lower;
}
cube[lower_cube].count = cube[lower_parent].count+1;
//同时更新最下方那个块的下边，就是下边stack的最上边的块
cube[lower_cube].lower = lower_parent;

//更新下方所有块的父节点，此时成为一个大的堆
while(cube[lower_parent].lower!=0)
{
cube[lower_parent].parent = parent;
lower_parent = cube[lower_parent].lower;
}
cube[lower_parent].parent = parent;
}

int main()
{
//有P个操作
int P;
//命令的种类，
//M X Y ,将X立方体所在的堆移到Y立方体所在的堆的上面
//C X 输出在X所在的堆上,在X立方体下面的立方体个数。
char ch;
int x,y;
init();
scanf("%d",&P);
while(P--)
{
scanf("\n%c",&ch);
//getchar();
//cin>>ch;
if(ch=='M')
{
scanf("%d%d",&x,&y);
union_set(x,y);//合并集合
}
else if(ch=='C')
{
scanf("%d",&x);
printf("%d\n",cube[x].count);
}
}
return 0;
}```

```#include <iostream>
#include <stdio.h>
#define MAXNUM 30010
using namespace std;

typedef struct
{
int count;//记录改立方体下方所有的立方体个数
int parent;//指向立方体所在堆最上边的那个立方体
int num;
}Cube;
Cube cube[MAXNUM];

void init()
{
for(int i = 1;i < MAXNUM; i++)
{
cube[i].count = 0;//初始化每个立方体下方均为0
cube[i].num = 1;
cube[i].parent = -1;//初始化每个立方体为单个堆，并且为当前堆最下边位置
}
}
int find(int a)
{
//自己指向自己，说明自己是根
if(cube[a].parent == -1)
return a;
int tem = cube[a].parent;
cube[a].parent = find(cube[a].parent);//压缩路径，使得所有的根是同一个
cube[a].count += cube[tem].count;//更新当前的块下方的数目，是
return cube[a].parent;//返回终极根
}

void union_set(int x,int y)
{
cube[x].parent = y;
cube[x].count += cube[y].num;
cube[y].num += cube[x].num;
}

int main()
{
//有P个操作
int P;
//命令的种类，
//M X Y ,将X立方体所在的堆移到Y立方体所在的堆的上面
//C X 输出在X所在的堆上,在X立方体下面的立方体个数。
char ch;
int x,y,rx,ry;
init();
scanf("%d",&P);
while(P--)
{
// scanf("%s",ch);
cin>>ch;
if(ch=='M')
{
scanf("%d%d",&x,&y);
rx = find(x);
ry = find(y);
if(rx!=ry)
union_set(rx,ry);//合并集合
}
else if(ch=='C')
{
scanf("%d",&x);
find(x);
printf("%d\n",cube[x].count);
}
}
return 0;
}```

+ 关注