Javascript: Connected Graph Components (2021)

Prompt

You have a graph of n nodes.

You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Questions

  • What constitutes a connected component?

Insights

  • We can unite common/valid groups into components using a disjoint set data structure.
  • Once we've done this, we simply need to count the number of unique root nodes (self-parent) across our groups.

Approach

  • Define a component counter (components).
  • Create a disjoint set with n nodes.
  • Unify disjoint components using edges.
  • If we find a node that is its own parent, this signifies the root of a unique component.
  • In this case, add to components counter.
  • Return components count.

Complexity

Time: O(n^3)
Space: O(n)

Solution

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */

var countComponents = function(n, edges) {
  // Define component count
  let components = 0;

  // Define a disjoint set with size (n)
  const uf = new UnionFind(n);

  // For all connections, unite elements in disjoint set
  for (const [x, y] of edges) uf.union(x, y);

  // Compute number of nodes with parent as self (indicates a unique component once edges are united)
  for (let i = 0; i < n; i++) {
    if (i === uf.find(i)) components++;
  }

  // Return component count
  return components;
};

class UnionFind {
  constructor(size) {
    this.root = Array(size).fill().map((_, i) => i);
    this.rank = Array(size).fill().map((_) => 1);
  }

  find(x) {
    if (x === this.root[x]) return x;
    this.root[x] = this.find(this.root[x]);
    return this.root[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.root[rootX] < this.root[rootY]) {
        this.root[rootX] = rootY;
      } else if (this.root[rootX] > this.root[rootY]) {
        this.root[rootY] = rootX;
      } else {
        this.root[rootY] = rootX;
        this.rank[rootX]++;
      }
    }
  }
}