Cube Stacking（并查集加递归）

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations: 
moves and counts. 
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y. 
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value. 

Write a program that can verify the results of the game. 

输入

* Line 1: A single integer, P 

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X. 

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

输出

Print the output from each of the count operations in the same order as the input file.

题目意思：把X那个整体搬到Y的那个整体上面 给出一个序号求其下面有多少块。

 

#include <bits/stdc++.h>
using namespace std;
int t;
const int N=300005;
int arr[N],sum[N],flood[N];

int find_root(int x){
    if(x==arr[x]) return arr[x];
    int temp=arr[x];   //保存前面地根
    arr[x]=find_root(arr[x]); //递归先改变后面的
    flood[x]+=flood[temp];  //到根的距离
    return arr[x];
}

void union_set(int x,int y){
    int xx=find_root(x);
    int yy=find_root(y);
    arr[yy]=xx;
    flood[yy]=sum[xx];
    sum[xx]+=sum[yy];
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    string name;
    int d1,d2;
    for(int i=1;i<=300004;i++){
        arr[i]=i;
        sum[i]=1;
        flood[i]=0;
    }
    while(t--){
        cin>>name;
        if(name[0]=='M'){
            cin>>d1>>d2;
            union_set(d1,d2);
        }
        else{
            cin>>d1;
            int zhi=find_root(d1);
            cout << sum[zhi]-flood[d1]-1 << endl;
        }
    }
    return 0;
}