并查集原理及应用

并查集，顾名思义，一个实现了合并和查询集合方法的数据结构。最常见的方式是用数组来实现。

并查集的最终目的是将输入的节点按照其连接关系，分割成一个或多个子集。一个简单的应用就是判断无向图的连通分量个数，或者判断无向图中任何两个顶点是否连通。

例如，节点 ① ② ③ ④，已知 ① 与 ② 相连， ② 与 ④ 相连，经过并查集操作，应该形成两个集合，其中一个集合是 {① ② ④}，另一个是 {③}。

并查集是怎样做到这件事的呢？它为每个集合推举了一个代表，如果通过查找操作发现两个节点的代表相同，则说明这两个节点同属一个集合。

我们已经提到过可以用数组来记录集合的合并情况，最初每个节点独立形成一个集合，节点本身就是集合的代表。并查集的合并操作根据节点的连通关系，将节点建立起父子关系，这时集合的代表就是父节点了。随着合并操作不断进行，亲缘关系越建越长，这时集合的代表就是这条链的最顶端节点（通过查找操作总可以递归找到它）：

1       3
 \
  2
   \
    4

这里要提醒的是，虽然我们使用了父子的概念，但我们的并查集底层维护的其实是一个数组，不是树，当然更不是集合。（就像堆，有人记错成二叉树，其实也是一个数组而已。）

练手：Leetcode 547. Friend Circles

class Solution {
public:
    int find(vector<int>& s, int x) {    // 查找根节点
        return s[x] == x? x: find(s, s[x]);
    }

    int findCircleNum(vector<vector<int>>& M) {
        int m = M.size();
        if (m != M[0].size()) return 0;

        vector<int> s;
        // 初始化 m 个独立子集合
        for (int i = 0; i < m; i++) s.push_back(i);

        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j < m; j++) {    // 遍历上三角即可
                if (M[i][j] == 1) {
                    int parent = find(s, j);
                    int child = find(s, i);
                                // 两个点连通但根节点却不同，需要进行连接
                    if (parent != child) s[child] = parent;
                }
            }
        }

        set<int> r;
        // 计算根节点个数
        for (int i = 0; i < m; i++) r.insert(find(s, s[i]));

        return r.size();
    }
};

以上代码存在一个问题，就是如果我们总把新节点添加到最后一层父节点的后面，很快查找操作就会变得费时。怎么样能改进现状呢？其实只要我们向上追溯能最终得到同一个代表就行，不一定要是线性的。

因此如果把查找根节点函数这一行稍加改动，每次都把原先存储的父节点值直接存储根节点值，这个集合的查找树就从单叉多层变为多叉单层的了：

int find(vector<int>& s, int x) {    // 查找根节点
    return s[x] == x? x: s[x] = find(s, s[x]);
}

查找的复杂度大大降低了！