題意：有n個元素，開始每個元素自己一棧，有兩種操作，將含有元素x的棧放在含有y的棧的頂端，合并為一個棧。第二種操作是詢問含有x元素下面有多少個元素。

?

6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4
輸出：

?

1 0 2

思路：這道題，說不上很難，額，解決它也的確花了比較長的時間。詢問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<iostream> #include<cstdio> #include<cstring> 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];elserank[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; } /* 110 M 12 14 M 15 16 M 16 17 M 12 17 C 17 */

?

總結

以上是生活随笔為你收集整理的poj1988（判断一个结点下面有多少个结点，推荐）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。