题目连接 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; }
HDU 2818 Building Block,布布扣,bubuko.com
原文：http://www.cnblogs.com/across-fun/p/3594784.html