Almost Union-Find（可删除元素的并查集）

【题目大意】

初始给定n个集合：{1},{2},…,{n}，要求支持三种操作：

1 "1 p q"：若p,q不在同一集合，将它们所在的集合合并成一个。

2 "2 p q"：若p,q不在同一集合，将元素p移动到q所在的集合。

3 "3 p" ：询问p所在集合的元素个数及元素和。

总共m个操作，1<=n，m<=10^5。

思路1：

维护sum[x],num[x]，表示用x表示的集合元素和及元素个数，这就可以解决操作1和3；

对于操作2，若直接把p的祖先变为pre(q)，假如p就是祖先就会导致p的孩子所在的集合也变为pre(q)所以这里不能直接对p做修改，就因为他是祖先，所以一个思路就是不再让集合内的元素做祖先，令pre[i]=i+n

而令pre[i+n] = i+n （n 为元素最多数目）作为祖先。这样就避免了上述问题。

代码1：

#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;

int pre[200010];
map <int,int> num;
map <int,int> sum;
int n;
void init()
{
    for(int i = 0; i <= n; i++)
    {
         pre[i]  = i+n;
         pre[i+n]= i+n;
         sum[i+n]= i;
         num[i+n]= 1;
    }
}

int find_(int x)
{
    return pre[x] == x ? x :(pre[x] = find_(pre[x]));
}

void join(int x,int y)
{
    int fx = find_(x);
    int fy = find_(y);
    if(fx != fy)
    {
        sum[fx] += sum[fy];
        num[fx] += num[fy];
        pre[fy] = fx;
    }
}

void move_(int x,int y)
{
   int fx = find_(x);
   int fy = find_(y);
   sum[fx] -= x;
   num[fx] --;
   sum[fy] += x;
   num[fy] ++;
   pre[x] = fy;
}

int main(){
    int q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        init();
        while(q--)
        {
            int mark,x,y;
            scanf("%d",&mark);
            if(mark == 1)
            {
                scanf("%d%d",&x,&y);
                join(x,y);
            }
            else if(mark == 2)
            {
                scanf("%d%d",&x,&y);
                move_(x,y);
            }
            else
            {
                scanf("%d",&x);
                int fx = find_(x);
                printf("%d %d\n",num[fx],sum[fx]);
            }
        }
    }
    return 0;
}

思路2：还可以偷梁换柱，添加一个数组id[],使每个数都有i 和 id[i]两纬状态，当要删除某个元素时，只要把他id[i]状态改变，使他的id从n+1开始建立新的单元集合。原状态用来存储原定关系不要改变，当查询，连接时，我们只查询连接id[]状态就可以了，i的状态只用来存路径。

#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;

int pre[200010];
map <int,int> num;
map <int,int> sum;
map <int,int> id;
int n,tal;
void init()
{
    for(int i = 0; i <= n; i++)
    {
         pre[i]= i;
         id[i] = i;
         sum[i]= i;
         num[i]= 1;
    }
    tal = n+1;
}

int find_(int x)
{
    return pre[x] == x ? x :(pre[x] = find_(pre[x]));
}

void join(int x,int y)
{
    int fx = find_(x);
    int fy = find_(y);
    if(fx != fy)
    {
        sum[fx] += sum[fy];
        num[fx] += num[fy];
        pre[fy] = fx;
    }
}

void move_(int x,int y)
{
   int fx = find_(id[x]);
   int fy = find_(id[y]);
   if(fx == fy) return;
   sum[fx] -= x;
   num[fx] --;
   id[x] = tal++;
   sum[id[x]] = x;
   num[id[x]] = 1;
   pre[id[x]] = id[x];
   join(id[x],id[y]);
}

int main(){
    int q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        init();
        while(q--)
        {
            int mark,x,y;
            scanf("%d",&mark);
            if(mark == 1)
            {
                scanf("%d%d",&x,&y);
                join(id[x],id[y]);
            }
            else if(mark == 2)
            {
                scanf("%d%d",&x,&y);
                move_(x,y);
            }
            else
            {
                scanf("%d",&x);
                int fx = find_(id[x]);
                printf("%d %d\n",num[fx],sum[fx]);
            }
        }
    }
    return 0;
}

秒客网

Almost Union-Find（可删除元素的并查集）

相关文章