首页 > 代码库 > 【poj 1988】Cube Stacking（图论--带权并查集 模版题）
【poj 1988】Cube Stacking（图论--带权并查集 模版题）
题意：有N个方块，M个操作｛“C x”：查询方块x上的方块数；“M x y”：移动方块x所在的整个方块堆到方块y所在的整个方块堆之上｝。输出相应的答案。
解法：带权并查集。每堆方块作为一个集合，维护3个数组：fa[x]表示x方块所在堆的最顶部的方块；d[x]表示x方块所在堆的最底部的方块；f[x]表示x方块方块x上的方块数。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=30010,M=100010; 8 int fa[N],f[N],d[N]; 9 char s[3];10 11 int ffind(int x)12 {//查找+更新 关于x的所有值13 if (fa[x]!=x)14 {15 int fx=fa[x];16 fa[x]=ffind(fx);17 f[x]+=f[fx];18 d[x]=d[fx];19 }20 return fa[x];21 }22 int main()23 {24 int n,m,x,y;25 scanf("%d",&m);26 for (int i=1;i<=N-10;i++) fa[i]=d[i]=i,f[i]=0;27 while (m--)28 {29 scanf("%s",s);30 if (s[0]==‘M‘)31 {32 scanf("%d%d",&x,&y);33 int fx=ffind(x),fy=ffind(y);34 fa[fy]=fx;//mainly 修改fy35 ffind(d[fx]);//更新了之后才可用36 f[fy]=f[d[fx]]+1;37 d[fx]=d[fy];//修改fx38 }39 else40 {41 scanf("%d",&x);42 int dx=d[ffind(x)];43 ffind(dx);//更新了才有保障44 printf("%d\n",f[dx]-f[x]);45 }46 }47 return 0;48 }
【poj 1988】Cube Stacking（图论--带权并查集 模版题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。