UVA11987 Almost Union-Find 题解

· · 题解

题目大意：

背景：

在这个问题中,你将实现一个与之相似的数据结构,但不完全相同,您需要编写的数据结构也是并查集,支持以下三种操作:

1 p q: 将包含 p 和 q 的集合进行合并,如果 p 和 q 已经在一个集合中,忽视此项操作。

2 p q: 将 p 移动至包含 q 的集合中,如果 p 和 q 已经在一个集合中,忽视此项操作。

3 p: 输出 p 所在集合的元素个数和总和。

初始时共有 n 个集合,分别为 \{ 1\},\{ 2\}...\{ n\}。

输入：

多组数据输入,对于每组数据第一行为两个整数 n,m (1 \leq n,m \leq 10^5) n 表示集合个数, m 表示操作总数.

下面 m 行每行为一种操作.对于每个操作 1 \leq p,q \leq n 。

输入以EOF结尾

输出：

对于每一组操作3输出集合元素个数和集合元素总和

思路：

看完题目我们可以想到（这和并查集模板差不多诶，拿过来改一下提交！！！），虽然这用到了并查集，但是它的第二个操作有毒。

第二个操作：一般人都会想用

fa[p] = find(q);

来做第二个操作，但是它有反例。

此时，输入

2 1 3

就会出现下面这种情况

哦豁 ，这时我们会发现，此时元素 2 也被添加到了集合中，是行不通的。分析一下原因，是因为 1 为根节点。解决方法：我们可以添加一个虚拟根节点，编号为 i + n 就可以了。至于为什么是正确的呢？在这位巨佬的博客中很详细地证明了，我就不再证明正确性了。

这个就是题目的难点了，学废了吗？

代码如下：

#include<bits/stdc++.h>
#define re register
using namespace std;
const int maxx = 2e5 + 10;
long long fa[maxx],sum[maxx],sz[maxx];
inline int find(int x){//查找父亲
    if(fa[x] == x){
        return x;
    }else{
        return fa[x] = find(fa[x]);
    }
}
int n,m;
int main(){
    while(scanf("%d %d",&n,&m) != EOF){//输入
        int p,q;
        for(re int i = 1;i <= n;i++){//初始化
            fa[i] = i + n;
        }
        for(re int i = n + 1;i <= n + n;i++){//初始化
            fa[i] = i;sz[i] = 1;sum[i] = i - n;
        }
        for(re int i = 1;i <= m;i++){
            int a;
            scanf("%d",&a);
            if(a == 1){//合并
                scanf("%d %d",&p,&q);
                int pp = find(p),qq = find(q);
                if(pp != qq){
                    fa[pp] = qq;
                    sum[qq] += sum[pp];
                    sz[qq] += sz[pp];
                }
            }else if(a == 2){//迁移p点
                scanf("%d %d",&p,&q);
                int pp = find(p),qq = find(q);
                if(pp != qq){
                    fa[p] = qq;
                    sz[pp]--;
                    sz[qq]++;
                    sum[pp] -= p;
                    sum[qq] += p;
                }
            }else{//输出p所在的集合里的点的数目和整个集合的大小
                scanf("%d",&p);
                int pp = find(p);
                printf("%lld %lld\n",sz[pp],sum[pp]);
            }
        }

    }
    return 0;
}