poj 1988 Cube Stacking 并查集的应用


这道题目题意是有有两种操作1、是将x移动到y的stack顶部。2、计数在x的stack中,在x之下的的cube个数。

主要思想是用arr[i]表示父亲节点,d[i]表示i之下有几个节点,s[i]表示以i为根的树共有几个节点。

在执行M时是直接找到a,b的父节点,然后合并,执行C时是查找答案。

#include<stdio.h>
#include<String.h>
#define maxn 300005
int p;
int arr[maxn],re[maxn],rank[maxn];
int find(int x)
{
if(arr[x]==x)
return x;
int temp =arr[x];
arr[x]=find(arr[x]);
rank[x]+=rank[temp];
return arr[x];
}
void merge(int x, int y)
{
x=find(x);
y=find(y);
arr[x]=y;
rank[x]+=re[y];
re[y]+=re[x];
re[x]=0;
}
int main()
{
int i,a,b;
char ch[5];
for(i=1;i<=maxn;i++)
{
re[i]=1;
rank[i]=0;
arr[i]=i;
}
scanf("%d",&p);
for(i=1;i<=p;i++)
{
scanf("%s",&ch);
//getchar();
if(ch[0]=='M')
{
scanf("%d%d",&a,&b);
merge(a,b);
}
if(ch[0]=='C')
{
scanf("%d",&a);
find(a);
printf("%d\n",rank[a]);
}
}
return 0;
}


 

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告