并查集

介绍

主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

理解

并查集的重要思想在于，用集合中的一个元素代表集合。有一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主

最开始，所有大侠各自为战。他们各自的帮主自然就是自己。（对于只有一个元素的集合，代表元素自然是唯一的那个元素）

现在1号和2号比武，假设1号赢了（这里具体谁赢暂时不重要），那么2号就认1号作帮主*（合并1号和2号所在的集合，1号为代表元素）*

同理，3号和4号比武，3号赢了，3号称为代表元素

最终，两大帮派一决高下，帮主1号和帮主3号比武，1号胜利，3号认1号为帮主，他的手下自然也跟着投降

class UnionFind {
    constructor(n) {
        // 一开始每个人都是帮主
        this.parent = new Array(n).fill(0).map((_, index) => index);
    }

    // 找到某个人的帮主
    find(index) {
        // 如果帮主就是自己，则证明找到了
        if (this.parent[index] === index) return index;

        // 否则递归往上找
        return this.find(this.parent[index]);
    }

    // 合并两个帮派， 这里以帮派1为主
    union(index1, index2) {
        let p1 = this.find(index1),
            p2 = this.find(index2);
        if (p1 !== p2) {
            this.parent[p2] = p1;
        }
    }
}

路径压缩

最简单的并查集效率是比较低的，在最差的情况下，会形成一条长链，如下图的左边

可以使用路径压缩的方法。既然只关心一个元素对应的根节点，那希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样下图的右边

其实这说来也很好实现。只要在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，就可以省很多事

class UnionFind {
    constructor(n) {
        // 一开始每个人都是帮主
        this.parent = new Array(n).fill(0).map((_, index) => index);
    }

    // 找到某个人的帮主
    find(index) {
        return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
    }

    // 合并两个帮派， 这里以帮派1为主
    union(index1, index2) {
        this.parent[this.find(index2)] = this.find(index1);
    }
}

并查集 ​

介绍 ​

理解 ​

路径压缩 ​

并查集

介绍

理解

路径压缩