Skip to content

归并排序#

目录#

1. 模板#

#include <iostream>
#include <string.h>
using namespace std;

const int num = 5e4 + 1;

int group[num];
int height[num];

// 初始化
void init_set()
{
    for (int i = 1; i < num; i++) {
        group[i] = i;
        // 树的高度
        height[i] = 0;
    }
}

// 查找
int find_set(int x)
{
    // 路径压缩
    if (x != group[x]) {
        group[x] = find_set(group[x]);
    }
    return group[x];
}

void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);

    // 简易做法
    // if (x != y)
    // {
    //     group[x] = group[y];
    // }

    // 合并优化做法
    if (height[x] == height[y]) {
        // 合并，树的高度加1
        height[x] = height[x] + 1;
        group[y] = x;
    } else {
        // 矮树合并到高树上，高树的高度保持不变
        if (height[x] < height[y]) {
            group[x] = y;
        }else{
            group[y] = x;
        }
    }
}

2. 题目#

并查集题目博客专栏

Back to top