Almost Union-Find
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 operations:
1 p q Union the sets containing p and q. If p and q are already in the same set,
ignore this command
2 p q Move p to the set containing q. If p and q are already in the same set,
ignore this command.
3 p Return 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
题意：
给你n个点m个操作，
有三种操作自己看吧
题解：
来自深渊小鱼的解答
此题最难处理的操作就是将一个单点改变集合，而普通的并查集是不支持这种操作的。
当结点p是叶子结点的时候，直接pa[p] = root(q)是可以的，
p没有子结点，这个操作对其它结点不会造成任何影响，
而当p是父结点的时候这种操作会破坏子节点的路径，因此必须保留原来的路径。
我们希望pa[p] = root(q)的同时又保留原来的路径，那么只需要在点上做一个标记，
如果这个点被标记，就沿着新的路径寻找。
此时在修改操作的时候这个点一定是叶子结点，所以可以直接pa[p] = root(q)，
而原来的点则变成一个虚点用来保留了原来的路径。
改变集合的操作以及查询都只涉及到单点，这个标记只影响这个点，在二次以及以上的寻找还是要按照原来的路径。
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include<vector> #include<queue> using namespace std; const int N = 1e5+20, M = 30005, mod = 1e9 + 7, inf = 0x3f3f3f3f; typedef long long ll; int fa[N],num[N],sum[N],fg[N],n,m,fa2[N]; int finds(int x,int d) { if(fg[x]&&d) return finds(fa2[x],0); else return x==fa[x]?x:fa[x]=finds(fa[x],0); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) fa[i] = i,num[i] = 1,fg[i] = 0, sum[i] = i; for(int i=1;i<=m;i++) { int x,a,b,y; scanf("%d",&x); if(x==3) { scanf("%d",&y); printf("%d %d ",num[finds(y,1)], sum[finds(y,1)]); } else { scanf("%d%d",&a,&b); if(x==1) { int fx = finds(a,1); int fy = finds(b,1); if(fx==fy) continue; fa[fx] = fy; num[fy] += num[fx]; sum[fy] += sum[fx]; } else { int fx = finds(a,1); int fy = finds(b,1); if(fx == fy) continue; num[fx]--; sum[fx]-=a; num[fy]++; sum[fy]+=a; fg[a] = 1; fa2[a] = fy; } } } } return 0; }