可并堆模板题-mergeable heap

Description

有n个点，第i个点标号为i，有两种操作：
0 x y 表示把x所在堆和y所在堆合并。
1 x 表示询问x所在堆的最小权。

Input

第一行两个整数n,m,表示有n个点m个操作。

接下来m行操作如题。

Output

对于每个询问操作输出其答案。

Sample Input

5 3

1 4

0 2 4

1 4

Sample Output

HINT

n，m<=100000

Solution

可并堆模板题，看到这道题第一眼裸并查集可做，但为了训练可并堆，此题我们采取可并堆来解决。(虽然还是得用并查集)

用并查集维护每个元素所在堆的根节点，合并即可。注意每次合并的应该是读入元素的根节点，而不是其本身。否则会导致每个点的根节点十分混乱，RE。同时合并的同时应该判断合并的两点是否属于同一个堆，如果是不用再合并，如果不是，则继续合并。

Code

#include <stdio.h>

#include <algorithm>

using namespace std;

int l[],r[],dis[],f[];

int merge(int x,int y)

{

    if(!x) return y;

    if(!y) return x;

    if(x>y)

        swap(x,y);

    r[x]=merge(r[x],y);

    f[r[x]]=x;

    if(dis[r[x]]>dis[l[x]])

        swap(l[x],r[x]);

    dis[x]=dis[r[x]]+;

    return x;

}

int find(int x)

{

    while(f[x])

        x=f[x];

    return x;

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    dis[]=-;

    for(int i=;i<=m;i++)

    {

        int a;

        scanf("%d",&a);

        if(a==)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            int t1=find(x);

            int t2=find(y);

            if(t1!=t2)

                merge(t1,t2);

        }

        if(a==)

        {

            int x;

            scanf("%d",&x);

            int t1=find(x);

            printf("%d\n",t1);

        }

    }

}

巴特西