并查集：连通性判定

// 运行环境：Node.js 14+
// 保存为 dsa-l14.js，执行：node dsa-l14.js

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i) // 初始各自为营
    this.rank = new Array(n).fill(0)                     // 树高估计
  }
  find(x) {                                   // 找根 + 路径压缩
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]] // 路径压缩：跳到爷节点
      x = this.parent[x]
    }
    return x
  }
  union(a, b) {                               // 按秩合并
    const ra = this.find(a), rb = this.find(b)
    if (ra === rb) return false              // 已同伙
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra
    else { this.parent[rb] = ra; this.rank[ra]++ }
    return true
  }
}

// 省份数量：n 个城市，isConnected[i][j]=1 表示相连
function provinces(isConnected) {
  const n = isConnected.length
  const dsu = new DSU(n)
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      if (isConnected[i][j]) dsu.union(i, j)
  let count = 0
  for (let i = 0; i < n; i++) if (dsu.find(i) === i) count++
  return count
}
console.log(provinces([[1,1,0],[1,1,0],[0,0,1]])) // 2（两个连通块）