首页 > 代码库 > 【uva11987】带删除的并查集
【uva11987】带删除的并查集
题意：初始有N个集合，分别为 1 ，2 ，3 .....n。有三种操件
1 p q 合并元素p和q的集合
2 p q 把p元素移到q集合中
3 p 输出p元素集合的个数及全部元素的和。
题解：
并查集。只是并查集中并没有删除的操作。所以就需要将删除的这个点的影响降到0，也就是给删除的点申请一个新的id，以后都是用这个新的id来表示这个点，这样原来的那个集合里的点p就没意义，自然影响就为0。
就我写了debug那里比较坑。。
代码：
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 typedef long long LL;
9 const int N=10*100100;
10 int n,m,tot,id[N],fa[N],cnt[N];
11 LL sum[N];
12
13 int findfa(int x)
14 {
15 if(fa[x]==x) return x;
16 return findfa(fa[x]);
17 }
18
19 int main()
20 {
21 freopen("a.in","r",stdin);
22 freopen("a.out","w",stdout);
23 while(scanf("%d%d",&n,&m)!=EOF)
24 {
25 for(int i=1;i<=n;i++) id[i]=i,fa[i]=i,cnt[i]=1,sum[i]=i;
26 tot=n;
27 for(int i=1;i<=m;i++)
28 {
29 int tmp,x,y,xx,yy;
30 scanf("%d",&tmp);
31 if(tmp==1)
32 {
33 scanf("%d%d",&x,&y);
34 xx=findfa(id[x]);yy=findfa(id[y]);
35 if(xx==yy) continue;//debug
36 fa[xx]=yy;
37 sum[yy]+=sum[xx];
38 cnt[yy]+=cnt[xx];
39 sum[xx]=0;cnt[xx]=0;
40 }
41 if(tmp==2)
42 {
43 scanf("%d%d",&x,&y);
44 xx=findfa(id[x]);yy=findfa(id[y]);
45 tot++;
46 id[x]=tot;
47 fa[tot]=yy;
48 sum[yy]+=(LL)x;
49 cnt[yy]++;
50 sum[xx]-=(LL)x;
51 cnt[xx]--;
52 }
53 if(tmp==3)
54 {
55 scanf("%d",&x);
56 xx=findfa(id[x]);
57 printf("%d %lld\n",cnt[xx],sum[xx]);
58 }
59 // for(int j=1;j<=n;j++)
60 // {
61 // printf("%d fa = %d cnt = %d sum = %d\n",j,fa[id[j]],cnt[id[j]],sum[id[j]]);
62 // }
63 // printf("\n");
64 }
65 }
66
67 return 0;
68 }
【uva11987】带删除的并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。