题意：有n个元素，开始每个元素自己一栈，有两种操作，将含有元素x的栈放在含有y的栈的顶端，合并为一个栈。第二种操作是询问含有x元素下面有多少个元素。
6M 1 6C 1M 2 4M 2 6C 3C 4 输出：
102 思路：这道题，说不上很难，额，解决它也的确花了比较长的时间。询问x元素下面有多少个元素，那么我只需要统计x元素上面有多少个元素，再用x所在的并查集的根节点的元素个数减去x元素上面的元素个数， 结果就出来了......当然，还是有些细节地方要说说的，在路径压缩的时候，有个rang[][3]，其中rank[x][0]，代表元素x上面有多少个元素，rank[x][1]代表元素x下面有多少个元素，rank[x][2]判断x元素 是否为某个子并查集的根节点。 如果某个结点x的父亲结点y曾经为某一个子并查集的根节点，那么，说明对于这个结点x已经是在y为根节点的时候压缩过了，那么当y不为根节点了，就不必再重新x对y的路径了，只需要直接更新，x对于新的根节点的路径
#include#include #include using namespace std;int father[30005],rank[30005][3];int flag=0;int find(int x){ if(rank[x][0]==0) rank[x][2]=1; if(x==father[x]) return x; int tmp=father[x]; father[x]=find(father[x]); int root=father[x]; if(tmp==root) { rank[root][1]+=rank[x][1]; rank[x][1]=0; //if(rank[root]) /*if(flag==1) { printf("1: %d %d %d %d\n",x,tmp,rank[x][0],rank[tmp][0]); }*/ } else { rank[root][1]+=rank[x][1]; rank[x][1]=0; if(rank[tmp][2]==1) //曾经为某一颗子并查集的根结点，那么它下面的结点直接+上根节点的值就是 rank[x][0]+=rank[tmp][0]; else rank[x][0]=rank[tmp][0]+1; /*if(flag==1) { printf("2: %d %d %d %d\n",x,tmp,rank[x][0],rank[tmp][0]); }*/ } return root;}void liantong(int tmp,int tmp1){ int x=find(tmp); int y=find(tmp1); father[y]=x; rank[y][0]=rank[x][1]; rank[x][1]+=rank[y][1]; rank[y][1]=0;}int main(){ int n; scanf("%d",&n); { for(int i=0; i<=30001; i++) { father[i]=i; rank[i][0]=0; rank[i][1]=1; rank[i][2]=0; } while(n--) { char ch[10]; scanf("%s",ch); if(ch[0]=='M') { int tmp,tmp1; scanf("%d%d",&tmp,&tmp1); int x=find(tmp); int y=find(tmp1); if(x!=y) liantong(tmp,tmp1); // find(tmp); // find(tmp1); } else { int k; scanf("%d",&k); if(k==17) flag=1; int ans=rank[find(k)][1]; /*if(rank[k][0]==0) printf("%d\n",rank[k][1]-1); else*/ printf("%d\n",ans-rank[k][0]-1); } } } return 0;}/*110M 12 14M 15 16M 16 17M 12 17C 17*/