MENU

并查集及其优化

July 12, 2020 • Read: 71 • 算法

并查集及其优化算法

并查集是一种树形的数据结构,用于处理一些不交集的合并以及查询问题,他的核心有两个:

  • find :用于确定一个子节点的根节点
  • union :用于合并两个子节点的根节点

例子:

image-20200712224447566

为确定D和F是否拥有同一个根节点,使用find函数,传入参数D和F,如果返回值相同,则拥有同一个根节点,否则拥有不同根节点,用伪码表示如下:

find(D) == find(F) // 拥有同一根节点
find(D) != find(F) // 拥有不同根节点

对于合并呢,则是:

image-20200712225151693

我们将 find 和 union转换为C代码

int parent[100];

int findRoot(int x) {
    return parent[x] == x ? x : find(X);
}

void unionRoot(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);
    
    parent[p1] = p2;
}

但是上面的代码却有很严重的问题!!!

因为创建树的方式太随意,所以会有可能创建出非常不平衡的树,使得树的秩过大,导致超时,那么我们就需要有一点优化

优化1:路径压缩

路径压缩是最简单的优化了,只需要修改 find 函数即可

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

原理:将两个数的节点全部连接到根上,类似于这样

image-20200712230238764

优化2:按秩合并

按秩合并只需要修改union的代码:

int parent[100];
int ranks[100];
void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);
    
    if (ranks[p1] > ranks[p2]) {
        parent[p1] = p2;
    } else {
        parent[p2] = p1;
        if (ranks[p1] == ranks[p2]) {
            ranks[p2]++;
        }
    }
    
}

原理:两个秩相同的树合并时秩加一,两个秩不同的树合并时秩不变,因此尽量将秩小的树放到秩大的树下,能够生产比较合理的一棵树

完整代码:

例题:洛谷P3367

路径压缩优化版

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-12 21:48:42
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 * @ 未优化版
 */ 

#include <bits/stdc++.h>
using namespace std;

int parent[10000];

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);
    
    // parent[find(x1)] = find(x2);
    parent[p1] = p2;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        int fun, x1, x2;
        scanf("%d%d%d", &fun, &x1, &x2);
        if (fun == 1) {
            toUnion(x1, x2);
        } else {
            find(x1) == find(x2) ? printf("Y\n") : printf("N\n");
        }
    }
    return 0;
}

双重优化版

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-12 21:57:50
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 * @ 优化版
 */ 

#include <bits/stdc++.h>
using namespace std;

int parent[10000];
int ranks[10000];

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
    // 使用三元运算符的时候一定要看清楚,别写错了
}

void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);
    
    if (ranks[p1] > ranks[p2]) {
        parent[p1] = p2;
    } else {
        parent[p2] = p1;
        if (ranks[p1] == ranks[p2]) {
            ranks[p2]++;
        }
    }
    
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }

    for (int i = 1; i <= m; i++)
    {
        int fun, x1, x2;
        scanf("%d%d%d", &fun, &x1, &x2);
        if (fun == 1) {
            toUnion(x1, x2);
        } else {
            find(x1) == find(x2) ? printf("Y\n") : printf("N\n");
        }
    }
    return 0;
}
Archives Tip
QR Code for this page
Tipping QR Code