1
// this is a very common disjoint set implement
2
function DS(n) {
3
  var root = [...new Array(n).keys()];
4
  var rank = new Array(n).fill(0);
5
  this.find = function (v) {
6
    if (root[v] !== v) root[v] = this.find(root[v]);
7
    return root[v];
8
  };
9
  this.union = function (i, j) {
10
    var [ri, rj] = [this.find(i), this.find(j)];
11
    if (ri === rj) return;
12
    if (rank[ri] > rank[rj]) root[rj] = ri;
13
    else if (rank[ri] < rank[rj]) root[ri] = rj;
14
    else (root[ri] = rj), rank[rj]++;
15
  };
16
  // get how many unique unions
17
  this.getUnoinCount = function () {
18
    for (var i = 0; i < n; i++) this.find(i);
19
    return new Set(root).size;
20
  };
21
}
22

23
function getKeys(i, j, n) {
24
  var val = i * n + j;
25
  val *= 2;
26
  // left and right part key of grid[i][j]
27
  return [val, val + 1];
28
}
29

30
/**
31
 * @param {string[]} grid
32
 * @return {number}
33
 */
34
var regionsBySlashes = function (grid) {
35
  var n = grid.length;
36
  if (n === 1) return grid[0][0] === " " ? 1 : 2;
37
  var ds = new DS(n * n * 2);
38
  for (var i = 0; i < n; i++) {
39
    for (var j = 0; j < n; j++) {
40
      var [left, right] = getKeys(i, j, n);
41
      // When this cell is ' ', union left and right.
42
      if (grid[i][j] === " ") ds.union(left, right);
43
      // if have upper neighbor
44
      if (i !== 0) {
45
        var [upLeft, upRight] = getKeys(i - 1, j, n);
46
        // For upper neighbor, if it's '/', we should choose right part to union, if '\', choose left.
47
        var upKey = grid[i - 1][j] === "\\" ? upLeft : upRight;
48
        // For current cell, if it's '/', we should choose left part to union, if '\', choose right.
49
        var curKey = grid[i][j] === "/" ? left : right;
50
        ds.union(upKey, curKey);
51
      }
52
      // if have left neighbor
53
      if (j !== 0) {
54
        var [leftLeft, leftRight] = getKeys(i, j - 1, n);
55
        // just choose the right part of the left neighbor
56
        var leftKey = leftRight;
57
        // just choose the left part of the current cell
58
        var curKey = left;
59
        ds.union(leftKey, curKey);
60
      }
61
    }
62
  }
63
  return ds.getUnoinCount();
64
};