网站建设财务计划与预测,哪些网站是php,瑶海区网站建设公司,网站建立价格题意#xff1a;求出每个集合的元素个数#xff0c;及总和#xff0c;给出三个操作#xff1a;
1 将含有a元素和b元素的集合合并#xff1b;2 将a元素放入含有b元素的集合中#xff1b;3 输出a元素所在集合的元素个数及总和#xff1b;
思路#xff1a;正常并查集求出每个集合的元素个数及总和给出三个操作
1 将含有a元素和b元素的集合合并2 将a元素放入含有b元素的集合中3 输出a元素所在集合的元素个数及总和
思路正常并查集与并查集元素的删除
题目
I hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identical. The data structure you need to write is also a collection of disjoint sets, supporting 3 operati
1 p qUnion the sets containing p and q. If p and q are already in the same set, ignore this command.2 p qMove p to the set containing q. If p and q are already in the same set, ignore this command.3 pReturn the number of elements and the sum of elements in the set containing p
Initially, the collection contains n sets: {1}, {2}, {3}, . . . , {n}.
Input
There are several test cases. Each test case begins with a line containing two integers n and m (1 ≤ n, m ≤ 100, 000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1 ≤ p, q ≤ n. The input is terminated by end-of-file (EOF).
Output
For each type-3 command, output 2 integers: the number of elements and the sum of elements.
Explanation
Initially: {1}, {2}, {3}, {4}, {5}
Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}
Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3})
Collection after operation 1 3 5: {1,2}, {3,4,5}
Collection after operation 2 4 1: {1,2,4}, {3,5}
Sample Input
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
Sample Output
3 12
3 7
2 8
/*对于删除操作在完美的并查集中所有节点都直接连接在根节点上理论上只要把要删除的节点的上级重新指向自己就可以了。
但是实际情况中我们的并查集形成的树的形态都是不可预估形态的如果直接将一个节点指向自己可能会将他的“下级”和他一起删除这就和我们的想法违背了。
所以在一个需要删除的并查集中初始化时就要处理一下
首先可以将每一个点都设立一个虚拟父节点这样根节点就是我们设立的虚拟节点类似于将每个节点放到一个盒子中
如果删除某点那么可以修改当前节点的父节点来导致当前点的孤立即删除时把这个节点从当前盒子拿出来放到另一个盒子中。
由于节点之间都是通过盒子来确定关系的所以盒子中元素是否存在并不影响节点之间的关系。*/
#includeiostream
#includecstdlib
#includecstring
#includecstdio
#includequeue
#define Lint long long int
using namespace std;
const int MAXN200010;
int f[MAXN];/*盒子内的元素链接*/
int sum[MAXN];/*集合内元素之和*/
int p[MAXN];/*盒子*/
int siz[MAXN];/*集合内元素个数下标为盒子下标*/
int n,m,cnt;
int find(int x)
{return xf[x] ? f[x] : f[x]find( f[x] ) ;
}
int main()
{int opt,u,v,x,y;while( scanf(%d%d,n,m)!EOF )//删除节点就是把原先的节点设置为虚点然后把点的位置用num数组指向新的位置。{cntn;for(int i1; in; i) f[i]p[i]sum[i]i,siz[i]1;for(int i1; im; i){scanf(%d,opt);if( opt1 ){scanf(%d%d,u,v);up[u],vp[v];ufind( u ),vfind( v );if( uv ) continue ;f[u]v;siz[v]siz[u],sum[v]sum[u];}if( opt2 ){scanf(%d%d,u,v);xfind( p[u] ),yfind( p[v] );if( xy ) continue ;sum[x]-u,siz[x]--;/*盒子的名称不变除去该元素*/xp[u]cnt;/*重新申请一个内存里面只有要操作的元素改变该元素的祖先*/f[x]y;sum[y]u,siz[y];}if( opt3 ){scanf(%d,u);ufind( p[u] );printf(%d %d\n,siz[u],sum[u]);}}}return 0;
}
