Count the Number of Complete Components - Union Find [JS]

Description 

Solution: Union Find

Use union find to find each connected component.
For each connected component, find the number of nodes and edges in the group.
The number of edges needed for a complete connected component = ((groupSize - 1) * groupSize) / 2

n = number of nodesm = number of edges
Time Complexity: O(n + m)
Space Complexity: O(n)

var countCompleteComponents = function(n, edges) {
  let uf = new UnionFind(n);
  for (let [a, b] of edges) {
    uf.union(a, b);
  }
  let groupSize = {};
  for (let i = 0; i < n; i++) { // find the number of nodes in each connected component
    let parent = uf.find(i);
    groupSize[parent] = (groupSize[parent] || 0) + 1;
  }
  let count = {};
  for (let [a, b] of edges) { // find the number of edges in each connected component
    let parent = uf.find(a); // parent of a = parent of b (since a and b are connected)
    count[parent] = (count[parent] || 0) + 1;
  }
  let complete = 0;
  for (let parent in groupSize) { // find the number of complete connected components
    let edgesCount = count[parent] || 0;
    let size = groupSize[parent];
    if (edgesCount === ((size - 1) * size) / 2) complete++;
  }
  return complete;
};

class UnionFind {
  constructor(size) {
    this.root = Array(size);
    this.rank = Array(size)
    for (var i = 0; i < size; i++) {
      this.root[i] = i;
      this.rank[i] = 1;
    }
  }
  // recursively finding the root of x, setting roots of all along the path to the root from bottom up.
  find(x) {
    if (this.root[x] === x) {
      return x;
    }
    return this.root[x] = this.find(this.root[x]);
  }
  // choose side whose rank (height) is smaller to set as root out of (x, y)
  // if the heights are equal, set it either way (set x as root for simplicity) and increase rank of x by one.
  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.root[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.root[rootX] = rootY;
      } else {
        this.root[rootY] = rootX;
        this.rank[rootX]++;
      }
    }
  }
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

Comments

Popular posts from this blog

Maximum Value of an Ordered Triplet II - Two Solutions [JS]

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

Sum of Prefix Scores of Strings - Trie [JS]

Maximum Count of Positive Integer and Negative Integer - Binary Search [JS]

Count Subarrays With Median K - Count Left & Right Balance [JS]