并查集

并查集

用集合中的某个元素来代表这个集合，该元素称为集合的代表元。
一个集合内的所有元素组织成以代表元为根的树形结构。
对于每一个元素parent[x]指向 x 在树形结构上的父亲节点。如果 x 是根节点，则令parent[x] = x。
对于查找操作，假设需要确定 x 所在的的集合，也就是确定集合的代表元。可以沿着parent[x]不断在树形结构中向上移动，直到到达根节点。

节点表示：

var maxSize = 1000000
var parent = [] // 父亲节点数组
var rank = [] // 深度数组
var data = [] // 数据数组

初始化时都设置 parent 为自己的标号：

function makeSet(i) {
  parent[i] = i
  rank[i] = 0
}

查找：

function findSet(i) {
  if (parent[i] == i) return parent[i]
  return findSet(parent[i])
}

合并：

function union(i, j) {
  i = findSet(i)
  j = findSet(j)
  if (i == j) return
  if (rank[i] > rank[j]) {
    parent[j] = i
  } else {
    if (rank[i] == rank[j]) rank[j]++
    parent[i] = j
  }
}