今天效率还不错，再接再厉^-^
总得来说，这道题目不难，但悲剧的是，我一开始理解错题意了
题意：1)n个队列，n个立方体。
2)初始化时候每个队列有一个立方体。
3）两个操作：m x y：将x所在的集合放到y所在的集合里面，说白了，就是将y所在集合放到x所在集合后面
c x：问x立方体下面有多少个立方体
呵呵，发现，其实，每次“真正”执行find（）的时候，实际上都是对Union的进一步维护，只有进行一次与节点x有关的Union时，才会对x维护，而且，维护过后，x节点之上的节点也会同时被维护，并且直接挂到根节点上，这意味着之后对另一些点的维护并不会影响到已维护了的节点
还有就是那个计算，节点x之下的元素个数=x所在集合的元素个数-x之上的元素-1，很好理解吧
更具体的解释，见代码：
#include<stdio.h> #define MAXN 30010 int f[MAXN],r[MAXN],above[MAXN]; //f[]记录父节点，r[a]记录元素a所在集合的元素个数，above[a]记录a之上 的元素个数 void init()//初始化 { int i; for(i=1;i<=MAXN;i++) { f[i]=i; r[i]=1; above[i]=0; } } int find(int x) { if(x==f[x]) return f[x]; int t=find(f[x]); above[x]+=above[f[x]]; f[x]=t; return f[x]; }//查找根节点，路径压缩，同时维护above[]的值，同样，还是留意一下递归过程，你会发现一个很重要的东西 //类似于回溯，到根节点之后，回溯的时候，每一个元素都直接挂到根节点上了 //这样也就避免了重复操作，呵呵，其实这也是路径压缩的关键所在 void Union(int x,int y) { int a=find(x); int b=find(y); if(a==b) return ; above[b]=r[a]; r[a]+=r[b]; f[b]=a; }//将y所在集合挂到x所在集合，虽说是挂在元素x所在集合的后面，实际上是直接挂在根节点上 //这也引出了一个词，"逻辑上的距离"，above记录节点到根节点逻辑上的距离 int main() { int i,a,b,n; char ch[2]; scanf("%d",&n); init(); for(i=1;i<=n;i++) { scanf("%s",ch); if(ch[0]=='M') { scanf("%d %d",&a,&b); Union(a,b); } else { scanf("%d",&a); printf("%d\n",r[find(a)]-above[a]-1); } } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/05/08/2040562.html
相关资源：算法艺术与信息学竞赛题目完全解析