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). The size of input file does not exceed 5MB.
Output
For each type-3 command, output 2 integers: the number of elements and the sum of elements.
Sample Input
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4x
3 3
Output for the Sample Input
3 12
3 7
2 8
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}
思路:并查集删除。被删除的节点的关系不能在原集合里删除,因为其子节点需要它来和爷爷节点联系。通过建立虚拟节点。
在没删除之前的操作就用id[x]代替x。如果有删除操作,之后对x的操作就是在对id[x]进行操作。
PS:真正的并查集删除操作是不存在的,建立虚拟编号相当于克隆了一个“被删除”的节点,原来的集合里还是存在“被删除”的节点的。只是以后只调用编号了而不会调用真正的节点本身。
#include<cstdio> using namespace std; int pre[200005],num[200005],sum[200005],id[100005];//id为虚拟编号节点 int n,m,l; void init(){ l=n; for(int i=0;i<=n;i++){ sum[i]=pre[i]=id[i]=i; num[i]=1; } } int find(int x){ while(pre[x]!=x){ int r=pre[x]; pre[x]=pre[r]; x=r; } return x; } void merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) { pre[fx]=fy; num[fy]+=num[fx]; sum[fy]+=sum[fx]; } } void move(int x){ int fx=find(id[x]);// 移走后id[x]被更新,但pre[x]不能被更新,要保留,所以只能用虚拟节点! sum[fx]-=x; num[fx]--; id[x]=++l; //x是第l-n个被删除的节点 sum[id[x]]=x; num[id[x]]=1; pre[id[x]]=id[x]; } int main(){ int d,p,q; while(~scanf("%d%d",&n,&m)){ init(); while(m--){ scanf("%d%d",&d,&p); if(d==1){ scanf("%d",&q); merge(id[p],id[q]); } else if(d==2){ scanf("%d",&q); if(find(id[p])!=find(id[q])){ move(p); merge(id[p],id[q]); } } else{ int fp=find(id[p]); printf("%d %d ",num[fp],sum[fp]); } } } return 0; }