[Javascript] Union Find with disjoint set rank optimization
Haven\'t touched UF for a while, use this as a point to write a general implementation for disjoint sets. \n\nMost folks do is use an array of integer for paren
Haven\'t touched UF for a while, use this as a point to write a general implementation for disjoint sets. \n\nMost folks do is use an array of integer for parents. Instead used map and don\'t initiazlize the size of DS in the beginning, so the class is a little more inclusive. For this problem we are giving the nodes as integer, but if I am going to present this problem with alphabetic letters, the array solution would have to create a map and reverse map for coding/decoding.\n\nHere is the code:\n\n```\n/**\n * @param {number} n\n * @param {number[][]} edgeList\n * @param {number[][]} queries\n * @return {boolean[]}\n */\nclass DisjointSet {\n  constructor (){\n    this.parents = {};\n    this.ranks = {};\n  }\n  \n  union (x, y) {\n    let xr = this.find(x), yr = this.find(y);\n    if(this.ranks[xr] < this.ranks[yr]){\n      this.parents[xr] = yr;\n    }else{\n      this.parents[yr] = xr;\n      if(this.ranks[xr] == this.ranks[yr]) this.ranks[yr] += 1\n    }\n  }\n  \n  find(x) {\n    if(!(x in this.ranks)){\n      this.parents[x] = x;\n      this.ranks[x] = 0;\n    }\n    if(this.parents[x] != x){\n      this.parents[x] = this.find(this.parents[x])\n    }\n    return this.parents[x];\n  }\n  \n  isConnected(x, y){\n    return this.find(x) == this.find(y)\n  }\n}\n// disjoint set with both sorted\nvar distanceLimitedPathsExist = function(n, edgeList, queries) {\n  edgeList.sort((a, b) => a[2] - b[2])\n  queries = queries.map((v, ind) => [...v, ind]).sort((a, b) => a[2] - b[2])\n  \n  let ds = new DisjointSet(), res = Array(queries.length).fill(false), i = 0, j = 0;\n  while(i < queries.length){\n    while(j < edgeList.length && queries[i][2] > edgeList[j][2]){\n      ds.union(edgeList[j][0], edgeList[j][1])\n      j++;\n    }\n    res[queries[i][3]] = ds.isConnected(queries[i][0], queries[i][1])\n    i++;\n  }\n  return res;\n};\n```
[]