Merging communities hackerrank solution

The “Merging Communities” problem on HackerRank is about maintaining and querying disjoint sets, often referred to as union-find or disjoint-set data structures. The problem typically requires efficiently merging communities and finding the size of communities that a given person belongs to.

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

    find(u) {
        if (this.parent[u] !== u) {
            this.parent[u] = this.find(this.parent[u]); // Path compression
        }
        return this.parent[u];
    }

    union(u, v) {
        const rootU = this.find(u);
        const rootV = this.find(v);

        if (rootU !== rootV) {
            if (this.size[rootU] < this.size[rootV]) {
                [rootU, rootV] = [rootV, rootU];
            }
            this.parent[rootV] = rootU;
            this.size[rootU] += this.size[rootV];
        }
    }

    getSize(u) {
        return this.size[this.find(u)];
    }
}

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let n, q;
const lines = [];
const uf = new UnionFind();

rl.on('line', (line) => {
    if (!n) {
        [n, q] = line.split(' ').map(Number);
        uf = new UnionFind(n);
    } else {
        lines.push(line);
    }
    if (lines.length === q) {
        lines.forEach((line) => {
            const parts = line.split(' ');
            if (parts[0] === 'M') {
                uf.union(Number(parts[1]), Number(parts[2]));
            } else if (parts[0] === 'Q') {
                console.log(uf.getSize(Number(parts[1])));
            }
        });
        rl.close();
    }
});

Explanation:

1. UnionFind Class: Implements the union-find data structure with path compression and union by size.
2. find: Finds the representative of the set containing u, with path compression to speed up future queries.
3. union: Merges the sets containing u and v. Uses union by size to keep the tree shallow.
4. getSize: Returns the size of the set containing u.