并查集

并查集是一个多棵树的数据结构(森林),每个节点记录一个father[i]表示它的父节点。并查集可以解决集合的合并和查询操作。

并查集的初始化代码如下:

1
2
3
4
void make_set() {
    for (int i = 0; i < n; ++i)
        father[i] = i;
}

此时每个节点都属于不同的集合。查询操作的代码如下:

1
2
3
int get_father(int v) {
    return father[v] != v ? get_father(father[v]) : v;
}

上面代码的意思就是,如果当前节点不是这棵树的根节点,那么就不断回溯到根节点。

接下来是合并操作:

1
2
3
4
void merge(int x, int y) {
    int root_x = find(x), root_y = find(y);
    if (root_x != root_y) father[root_x] = root_y;
}

下图是合并操作的图解:

并查集的一个优化叫做【路径压缩】,是在并查集执行查询时对经过的点进行【扁平化】的方法。优化后的代码如下:

1
2
3
4
int get_father(int v) {
    if (father[v] != v) father[v] = get_father(father[v]);
    return father[v];
}

打个小广告

欢迎加入我的知识星球「基你太美」,我会在星球中分享 AucFrame 框架、大厂面经、AndroidUtilCode 更详尽的说明…一切我所了解的知识,你可以通过支付进入我的星球「基你太美」进行体验,加入后优先观看星球中精华的部分,如果觉得星球的内容对自身没有收益,你可以自行申请退款退出星球,也没必要加我好友;如果你已确定要留在我的星球,可以通过扫描如下二维码(备注:基你太美+你的星球昵称)加我个人微信,方便我后续拉你进群(PS:进得越早价格越便宜)。

我的二维码