526互联

（来一套）JavaScript并查集模板

发布时间 2023-12-11 14:20:57作者: 樊顺

code: 

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = new Array(n).fill(1);
        this.cnt = n;
    }

    findset(x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }

    unite(a, b) {
        let x = this.findset(a);
        let y = this.findset(b);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.cnt -= 1;
        return true;
    }

    connected(a, b) {
        const x = this.findset(a);
        const y = this.findset(b);
        return x === y;
    }
}