并查集 2019年8月10日计蒜客联盟周赛 K.数组

题目链接：https://nanti.jisuanke.com/t/40860

题意：给一个长度为n的数组a[]，n<1e5，a[i]<1e5

三个操作：

1 x y：把所有值为x的数据改成a[y]

2 x：输出a[x]的值

3 x：值为x的树有多少个

 

官方解析：

设father[i]表示初值为i的元素，当前的值为多少。

设cnt[i]表示当前值为i的元素有多少。

用并查集维护这两个数组。

 

个人思路：

做这道题的人并不多，可能是想不到可以用并查集（那我+1）。

因为要将值为x的数据进行修改，所以fa[i]!=a[i]，而是存的i，即fa[i]=i（i从1到maxn）。

1操作把x和a[y]进行merge（merge中把x的size加给a[y]，x的size置为0，变成有size[x]+size[a[y]]个a[y]，0个x）。

但是如果size[x]已经是0了（有0个值为x的数，已经变成某个数tmp了），就不能把他和a[y]合并了，不然2操作查询a[x]就会输出是a[y]而不是tmp。【感谢starhai霸霸的指出】

2操作输出a[x]的祖宗结点，3操作输出size[x]。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int n,a[maxn];
int size[maxn],fa[maxn];
int get(int x)
{
    if(fa[x]==x){return x;}
    int y=fa[x];
    fa[x]=get(y);
    return fa[x];
}

void merge(int a,int b)
{
    a=get(a);
    b=get(b);
    if(a!=b)
    {
        fa[a]=b;
        size[b]+=size[a];
        size[a]=0;
    }
}

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        fa[a[i]]=a[i];
        size[a[i]]++;
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int op,x,y;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            if(size[x]) merge(x,a[y]);
        }
        else if(op==2)
        {
            scanf("%d",&x);
            printf("%d\n",get(a[x]));
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",size[x]);
        }
    }
    return 0;    
}

View Code

 

自用带权并查集模板

#include <iostream>
using namespace std;
int father[110],n;
int dist[110],size[110];
void init()
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i,dist[i]=0,size[i]=1;
    }
}
int get(int x){
    if(father[x]==x){return x;}
    int y=father[x];
    father[x]=get(y);
    dist[x]+=dist[y];
    return father[x];
}
void merge(int a,int b)
{
    a=get(a);
    b=get(b);
    if(a!=b)
    {    
        father[a]=b;
        dist[a]=size[b];
        size[b]+=size[a];
    }
}

int main() {
    n=10;init();  //每个节点刚开始的祖宗都是自己
    merge(1,2);  //1的根节点指向2的根节点，father[1的祖宗]=2的祖宗
    merge(10,7);
    merge(3,4);
    merge(3,7);
    get(1);  //找出1的祖宗
    cout<<dist[1]+1<<endl;  //size是包括自己的子孙个数，dist为元素到队首的距离
    get(3);
    cout<<dist[3]+1<<endl;
    return 0;
}

View Code

dist好像跟merge的顺序有关，mark一下，明天研究。