HDU 2818 Building Block

---

題目連接 http://acm.hdu.edu.cn/showproblem.php?pid=2818

題意:給定N個blocks，分在N個堆里，然后又P個操作，每次將x所在的堆放在y所在的堆上，或者詢問x的下面有幾個blocks

做法：帶權并查集

因為要查詢x的下面有多少blocks，所以我們在普通并查集的基礎上在維護兩個域size[x]和under[x]，分別表示x所在堆的大小以及x下面的元素。

在合并的時候，我們分別取x,y的堆的最下面一塊，也就是他們的根a,b.a和b相等就不用處理了。如果不相等，那么就讓F[a] = b.而在這之前，我們要維護size和under，所有x原來所在的堆的每個元素的under都要增加size[b],如果全都修改會超時，所以我們之修改under[a],把其它修改放在壓縮里面，要查哪一個再更新。同時，為了方便我們只把size存在根上，也就是size[b]+=size[a],size[a] = 0。

在find的時候，我們進行壓縮，這時候更新under[x],under[x]+=under[fx]就可以了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <functional>
#include <cmath>
typedef long long ll;
using namespace std;
const int MAXN = 30010;
int F[MAXN],size[MAXN],under[MAXN];
int f(int x){if(F[x] == x)return x;int fx = F[x];F[x] = f(F[x]);under[x]+=under[fx];return F[x];
}
void uni(int x,int y){int a = f(x),b = f(y);if(a == b)return ;under[a] += size[b];size[b]+=size[a];size[a] = 0;F[a] = b;
}
int main(){ios::sync_with_stdio(0);for(int i=0;i<MAXN;i++){F[i] = i;size[i] = 1;}int p;cin>>p;while(p--){char cmd;cin>>cmd;if(cmd == 'M'){int x,y;cin>>x>>y;uni(x,y);}else{int x;cin>>x;f(x);cout<< under[x] <<endl;}}return 0;
}