2019-07-17 并查集

作者: DreamNeverDie | 来源:发表于2019-07-17 16:55 被阅读0次

2019-07-17 并查集
markdown学习
算法模板(四)并查集
并查集入门使用
并查集练习
并查集
数据结构与算法（十二）并查集(Union Find)
并查集
并查集
并查集

<!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>