可并堆模板题-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

4

2

HINT

n，m<=100000

Solution

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

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

Code

#include <stdio.h>
#include <algorithm>
using namespace std;
int l[100100],r[100100],dis[100100],f[100100];
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]]+1;
    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[0]=-1;
    for(int i=1;i<=m;i++)
    {
        int a;
        scanf("%d",&a);
        if(a==0)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int t1=find(x);
            int t2=find(y);
            if(t1!=t2)
                merge(t1,t2);
        }
        if(a==1)
        {
            int x;
            scanf("%d",&x);
            int t1=find(x);
            printf("%d
",t1);
        }
    }
}