157
【北大夏令营笔记-并查集】poj1988-Cube Stacking
Cube StackingTime Limit: 2000MS Memory Limit: 30000K
Total Submissions: 18401 Accepted: 6378
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
USACO 2004 U S Open
并查集的应用
将每一堆当成一个集合，当这一堆压倒那一堆的时候，进行集合合并
AC代码：
#include<stdio.h>
#include<stdlib.h>
#define MAX 31000
int parent[MAX];
int sum[MAX];
int under[MAX];
int GetRoot(int a)
{
if(parent[a]==a)
return a;
int t=GetRoot(parent[a]);
under[a]+=under[parent[a]];
parent[a]=t;
return parent[a];
}
void merge(int a,int b)
{
//把b所在的堆，叠放到a所在的堆
a=GetRoot(a);
b=GetRoot(b);
if(a==b)
return;
parent[b]=a;
under[b]=sum[a];//under[b]赋值前一定是0，因为
//parent[b]=b,b一定是原b所在堆的最底下的
sum[a]+=sum[b];
}
int main()
{
int i,j,n;
for(i=0;i<MAX;i++)
{
sum[i]=1;
parent[i]=i;
under[i]=0;
}
scanf("%d",&n);
for(i=0;i<n;i++)
{
char s[20];
int a,b;
scanf("%s",s);
if(s[0]=='M'){
scanf("%d %d",&a,&b);
merge(b,a);
}else
{
scanf("%d",&a);
GetRoot(a);//进行矩阵压缩，更新以前没有更新的under值(加上父亲以及所有祖先的under值)
//最下面的那个是老祖宗，一般下面被压的的辈分比上面高
printf("%d\n",under[a]);
}
}
return 0;
}
最后更新：2017-04-03 05:39:19