2019-07-17 并查集

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 并查集
    class UnionFind {
        constructor(n) {
            this.parent = new Array(n);
            this.count = n;
            this.rank = new Array(n);
            for (let i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        find(p) {
            if (p < 0 || p >= this.count) return;
            let stack = [],
                cur = p,
                prev;
            // path compression 1
            // while (p !== this.parent[p]) {
            //     this.parent[p] = this.parent[this.parent[p]];
            //     p = this.parent(p);
            // }
            // return p
            // path compression 2
            // if (p !== this.parent[p]) {
            //     this.parent[p] = this.find(this.parent[p])
            // }
            while (cur !== this.parent[cur]) {
                stack.push(cur);
                cur = this.parent[cur]
            }
            while (stack.length) {
                this.parent[stack.pop()] = cur
            }
            return this.parent[p];
        }

        isConnected(p, q) {
            return this.find(p) === this.find(q)
        }

        unionElements(p, q) {
            let pId = this.find(p),
                qId = this.find(q);
            if (pId === qId) return;
            if (this.rank[pId] < this.rank[qId]) {
                this.parent[pId] = qId;
            } else if (this.rank[qId] < this.rank[pId]) {
                this.parent[qId] = pId;
            } else {
                this.parent[pId] = qId;
                this.rank[qId]++;
            }
        }
    }
</script>
</body>
</html>
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容