poj 1988 Cube Stacking 並查集

   也是個題意比較奇葩的題目。有2個操作，1個是把一個元素所在的棧，放到另外1個元素所在
的棧上面。另外一個操作是統計某個元素下面有多少個元素(當然是在同一個棧中）。
   貌似，需要記錄每個元素下面的元素是什麼了，既然要記錄這個就不能用並查集的路徑壓縮了。
 不壓縮路徑的話，肯定會超時的。怎麼辦了。。。
   其實，可以這麼考慮，以每個棧的棧底元素作為並查集的代表元素。壓縮路徑後，每個元素或者
是根元素或者其父親元素就是根元素。所以，另外對每個節點附加個信息代表該節點的高度，棧底
元素高度為0。再附加個信息代表每個並查集元素總數目，這樣就可以在合並集合時候修改信息，
並且壓縮路徑也能保證答案正確。。。

   代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 30010;
int nSets[MAX];
int nNum[MAX];
int nRank[MAX];

void MakeSets(int nN)
{
    for (int i = 0; i < nN; ++i)
    {
        nSets[i] = i;
        nNum[i] = 1;
        nRank[i] = 0;
    }
}

int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nRank[nI] += nRank[nPre];
    }
   
    return nSets[nI];
}

void Move(int nX, int nY)
{
    int nA = FindSet(nX);
    int nB = FindSet(nY);
    //printf("nA:%d,nB:%d\n", nA, nB);
    if (nA != nB)
    {
        nSets[nA] = nB;
        nRank[nA] += nNum[nB];
        nNum[nB] += nNum[nA];
    }
}

int main()
{
    int nP;
    char szOper[10];
    int nX, nY;

    scanf("%d", &nP);
    MakeSets(MAX);
    while (nP--)
    {
        scanf("%s", szOper);
        if (szOper[0] == 'M')
        {
            scanf("%d%d", &nX, &nY);
            Move(nX, nY);
        }
        else
        {
            scanf("%d", &nX);
            FindSet(nX);
            printf("%d\n", nRank[nX]);
        }
    }

    return 0;
}