Graph Connectivity With Threshold LeetCode solution in JavaScript

1
var areConnected = function (n, threshold, queries) {
2
  // if(gcd(a,b)>threshold), a and b are connected
3

4
  // 2 is connected with : 2, 4,6,8,10,12,14,16, (gcd(2,y)=2)
5
  // 3 is connected with : 3,6,9,12,... (gcd(3,y)=3)
6
  // 4 is connected with : 4,8,12,16,20,24,28, (gcd(4,y)=4)
7
  // 6 is connected with : 6,12,18...,cos (gcd(6,y)=6)
8
  // 5 is connected with : 10,15,20,25,...n cos (gcd(5,y)=6)
9
  // etc
10

11
  let dsu = new UnionFind(n + 1); //to map n=>n (no node 0 on my question)
12

13
  for (
14
    let node = threshold + 1;
15
    node <= n;
16
    node++ //basically this ensures that the road exists
17
  )
18
    //cos gcd(node,secondnode)==node >threshold
19
    for (let secondnode = node + node; secondnode <= n; secondnode += node)
20
      dsu.union(node, secondnode);
21

22
  return queries.map(([a, b]) => dsu.sameGroup(a, b));
23
};
24
class UnionFind {
25
  constructor(size) {
26
    //the total count of different elements(not groups) in this union find
27
    this.count = size;
28
    //tracks the sizes of each of the components(groups/sets)
29
    //groupsize[a] returns how many elements the component with root a has
30
    this.groupSize = [...Array(size)];
31
    //number of components(groups) in the union find
32
    this.numComponents = size;
33
    //points to the parent of i, if parent[i]=i, i is a root node
34
    this.parent = [...Array(size)]; //which is also the index of the group
35

36
    //put every element into its own group
37
    // rooted at itself
38
    for (let i = 0; i < size; i++) {
39
      this.groupSize[i] = i;
40
      this.parent[i] = i;
41
    }
42
  }
43

44
  //returns to which component (group) my element belongs to
45
  // (n) --Amortized constant time
46
  // Update: Also compresses the paths so that each child points to its
47
  // parent
48
  find(element) {
49
    let root = element;
50
    //find the parent of the group the elemnt belongs to
51
    // When root===parent[root] is always the parent of that group (root)
52
    while (root != this.parent[root]) root = this.parent[root];
53

54
    // Compression, point the element to its parent if its not already pointed
55
    // Tldr: Not only do I point my element to its actual root, i point any
56
    // inbetween elements to that root aswell
57
    while (element != root) {
58
      let next = this.parent[element];
59
      this.parent[element] = root;
60
      element = next;
61
    }
62

63
    return root;
64
  }
65

66
  //Unifies the sets containing A and B
67
  // if not already unified
68
  // (n) --Amortized constant time
69
  union(A, B) {
70
    let root1 = this.find(A), //parent of A
71
      root2 = this.find(B); //parent of B
72
    if (root1 === root2)
73
      //already unified
74
      return;
75
    // I want to put the set with fewer elements
76
    // to the one with more elemenets
77
    if (this.groupSize[root1] < this.groupSize[root2]) {
78
      this.groupSize[root2] += this.groupSize[root1];
79
      this.parent[root1] = this.parent[root2];
80
    } else {
81
      this.groupSize[root1] += this.groupSize[root2];
82
      this.parent[root2] = this.parent[root1];
83
    }
84

85
    this.numComponents--; //cos 1 less group, since i merged 2
86
  }
87

88
  //same parent=>samegroup
89
  sameGroup = (A, B) => this.find(A) == this.find(B);
90

91
  //essentially the groupSize of its parent's group
92
  sizeOfGroup = (A) => this.groupSize[this.find(A)];
93
}