并查集及其优化算法

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

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

例子：

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

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

对于合并呢，则是：

我们将 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]));
}

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

优化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;
}