并查集

并查集，顾名思义，其有两种功能，一是合并，二是查找。
我们用一个大小为 N 的数组 fa 来维护一个并查集，每个元素以编号作为它的唯一标识符，这 N 个元素的编号为 0 到 N-1.
fa[i] 的意义是元素 i 的父元素

并查集的初始化

初始化的并查集，所有的元素都是相互独立的，所有的元素的父元素都是自己。

function init() {
    let fa = [];
    for (let i = 0; i < N; i++) {
        fa[i] = i;
    }
}

查找

我对查找的理解是，找到并查集中元素 i 的根节点。对于某个元素而言，如果它的父元素就是自己，那它的根节点就是自己，如果父元素不是自己，就递归去找父元素的根节点。

function find(i) {
    if (fa[i] === i) {
        return i;
    } else {
        return find(fa[i]);
    }
}

合并

我对合并的理解是，使并查集中原本并没有连通的两个元素，连通。连通可以理解为，向上追溯，他俩拥有同一个根节点。合并的方法为，把元素 i 的根节点的父节点，设置成元素 j 的根节点。

function merge(i, j) {
    fa[find(i)] = find(j);
}