题意:初始有N个集合,分别为 1 ,2 ,3 .....n。有三种操件
1 p q 合并元素p和q的集合
2 p q 把p元素移到q集合中
3 p 输出p元素集合的个数及全部元素的和。
思路:并查集操作。1、3步比较容易实现,只要建立一个sum[],cnt[],记录每个结点相应值,和并时把值更新到根结点,输出时只要找到根结点输出其值即可。
但2操作有点麻烦,并查集没有删除操作。原先以为直接把p指向q的根就行了,但发现这是错的。如果p是叶子结点,那没问题,但如果是某个集合的根呢。我们只是要把这一个元素移掉,如果直接把p指向q的根,它的叶子结点也指向了。。。
换个思路,将p这个点对它所在的集合的“影响”将为0。然后再新开一个节点表示p这个节点就相当于把p从原来的集合中剥离出来了。因此相比原来的并查集,需要多一个id[p]数组表示点p现在的标号.
//0 KB 192 ms #include #include const int M = 200005; int pa[M],cnt[M],id[M]; //pa为集合,cnt总个数,id编号 long long sum[M]; //总和 int n,m,dep; void Init() { for (int i = 0;i <= n;i ++) sum[i] = pa[i] = id[i] = i,cnt[i] = 1; dep = n; } int findset (int x) { return x == pa[x] ? x :(pa[x] = findset (pa[x])); } void Union(int a,int b) { int af = findset (a); int bf = findset (b); pa[af] = bf,sum[bf] += sum[af]; cnt[bf] += cnt[af]; } void Move(int a) { int af = findset (id[a]); sum[af] -= a,cnt[af] --; id[a] = ++dep; //新开一个点 sum[id[a]] = a,cnt[id[a]] = 1,pa[id[a]] = id[a]; } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int op,a,b; while (scanf ("%d%d",&n,&m) == 2) { Init(); while (m --) { scanf ("%d",&op); switch(op) { case 1: scanf ("%d%d",&a,&b); if (findset(id[a]) != findset (id[b])) Union(id[a],id[b]); break; case 2: scanf ("%d%d",&a,&b); if (findset (id[a])!= findset (id[b])) Move(a),Union(id[a],id[b]); break; case 3: scanf ("%d",&a); int af = findset (id[a]); printf ("%d %lld\n",cnt[af],sum[af]); break; } } } return 0; }