专业网站建设品牌策,注册域名之后怎么做网站,应用开发用什么软件,wordpress android api题目连接 http://acm.hdu.edu.cn/showproblem.php?pid2818 题意:给定N个blocks#xff0c;分在N个堆里#xff0c;然后又P个操作#xff0c;每次将x所在的堆放在y所在的堆上#xff0c;或者询问x的下面有几个blocks 做法#xff1a;带权并查集 因为要查询x的下面有多少bl…题目连接 http://acm.hdu.edu.cn/showproblem.php?pid2818 题意:给定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 i0;iMAXN;i){F[i] i;size[i] 1;}int p;cinp;while(p--){char cmd;cincmd;if(cmd M){int x,y;cinxy;uni(x,y);}else{int x;cinx;f(x);cout under[x] endl;}}return 0;
}转载于:https://www.cnblogs.com/across-fun/p/3594784.html
