并查集（Union Find）结构是 二叉树结构 的衍生，用于高效解决无向图的连通性问题。 + 可以在O(1) 时间内合并两个连通分量，在O(1) 时间内查询两个节点是否连通，在O(1) 时间内查询连通分量的数量。

核心原理

并查集底层其实是一片森林（若干棵多叉树），每棵树代表一个连通分量： - connected(p, q)：只需要判断 p 和 q 所在的多叉树的根节点，若相同，则 p 和 q 在同一棵树中，即连通，否则不连通。 - count()：只需要统计一下总共有多少棵树，即可得到连通分量的数量。 - union(p, q)：只需要将 p 节点所在的这棵树的根节点，接入到 q 节点所在的这棵树的根节点下面，即可完成连接操作。注意这里是两棵树的合并，并不是 p, q 两个节点的合并。因为 p, q 一旦连通，那么他们所属的连通分量就合并成了同一个更大的连通分量。 综上，并查集中每个节点其实不在乎自己的子节点是谁，只在乎自己的根节点是谁，所以一个并查集节点类似于下面这样：

class UFNode { 
    // 节点 id 编号 
    int id; 
    // 指向父节点的指针 
    UFNode parent; 
}

这样，对于任意一个节点，我们都可以顺着 parent 指针一路找到它的根节点。union, connected, count 方法的实现思路如下：

// 连接节点 p 和节点 q
void union(UFNode p, UFNode q) {
    // 找到节点 p 和节点 q 的根节点
    // 将 p 所在的整棵树接到 q 所在的整棵树下面
    return find(p).parent = find(q);
}

// 查询节点 p 和节点 q 是否连通（是否在同一个连通分量内）
boolean connected(UFNode p, UFNode q) {
    return find(p) == find(q);
}

// 查询节点 node 的根节点，时间复杂度取决于树的高度
UFNode find(UFNode node) {
    while (node.parent != null) {
        node = node.parent;
    }
    return node;
}

并查集的优化

union 和 connected 方法的时间复杂度都依赖 find 方法，而 find 方法的时间复杂度取决于树的高度。

所以并查集算法最终的目标，就是要尽可能降低树的高度，如果能保持树高为常数，那么上述方法的复杂度就都是 O(1)O(1) 了。

在仔细观察即可发现，使得树高线性增长的原因是，特殊情况下每次 union 操作可能将节点个数较多的树接到了节点个数较少的树下面，这就很容易让树高增加，很不明智。

为了解决这个问题，一种优化思路是引入一个权重数组，记录以每个节点的为根的树的节点个数，然后在 union 方法中，总是将节点个数较少的树接到节点个数较多的树下面，这样可以保证树尽可能平衡，树高也就不会线性增长。

路径压缩

路径压缩优化方法，它可以让树高始终保持在常数级别，这样 union, connected, find 方法的时间复杂度都是 O(1)O(1)。