0323-number-of-connected-components-in-an-undirected-graph.js

/**
 * https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
 * Time O(V + E) | Space O(V + E)
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function (n, edges, count = 0) {
    const { graph, visited } = buildGraph(n, edges);

    for (const node in graph) {
        if (hasPath(graph, node, visited)) count++;
    }

    return count;
};

const initGraph = (n) => ({
    graph: new Array(n).fill().map(() => []),
    visited: new Array(n).fill(false),
});

const buildGraph = (n, edges) => {
    const { graph, visited } = initGraph(n)

    for (const [ src, dst ] of edges) {
        graph[src].push(dst);
        graph[dst].push(src);
    }

    return { graph, visited };
}

const hasPath = (graph, current, visited) => {
    if (visited[current]) return false;
    visited[current] = current;

    for (const neighbor of graph[current]) {
        hasPath(graph, neighbor, visited);
    }

    return true;
}

/**
 * https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
 * Time O(E * a(N)) | Space O(V)
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
 var countComponents = function(n, edges) {
    return new UnionFind(n, edges)
        .connectedComponents;
};

class UnionFind {
    constructor (n, edges) {
        this.parent = new Array(n).fill().map((_, index) => index),
        this.rank = new Array(n).fill(1)
        this.connectedComponents = n;

        this.search(edges);
    }

    search (edges) {
        for (const [ src, dst ] of edges) {
            this.union(src, dst)
        }
    }

    find (head, tail = head, { parent } = this) {
        const isEqual = () => head === parent[head]
        while (!isEqual()) {
            head = parent[head];
        }

        this.compress(tail, head);

        return head
    }

    compress (tail, head, { parent } = this) {
        parent[tail] = head;
    }
    
    increaseRank (head, tail, { rank } = this) {
        rank[head] += rank[tail];
    }

    union (src, dst, { rank } = this) {
        const [ rootSrc, rootDst ] = [ this.find(src), this.find(dst) ]

        const hasCycle = rootSrc === rootDst
        if (hasCycle) return

        this.connectedComponents--;

        const isGreater = rank[rootSrc] < rank[rootDst]
        if (isGreater) {
            this.increaseRank(rootDst, rootSrc)
            this.compress(rootSrc, rootDst)
        }

        const isLess = rank[rootDst] <= rank[rootSrc]
        if (isLess) {
            this.increaseRank(rootSrc, rootDst)
            this.compress(rootDst, rootSrc)
        }
    }
}