并查集，顾名思义，一个实现了合并和查询集合方法的数据结构。最常见的方式是用数组来实现。
并查集的最终目的是将输入的节点按照其连接关系，分割成一个或多个子集。一个简单的应用就是判断无向图的连通分量个数，或者判断无向图中任何两个顶点是否连通。
例如，节点 ① ② ③ ④，已知 ① 与 ② 相连， ② 与 ④ 相连，经过并查集操作，应该形成两个集合，其中一个集合是 {① ② ④}，另一个是 {③}。
并查集是怎样做到这件事的呢？它为每个集合推举了一个代表，如果通过查找操作发现两个节点的代表相同，则说明这两个节点同属一个集合。
我们已经提到过可以用数组来记录集合的合并情况，最初每个节点独立形成一个集合，节点本身就是集合的代表。并查集的合并操作根据节点的连通关系，将节点建立起父子关系，这时集合的代表就是父节点了。随着合并操作不断进行，亲缘关系越建越长，这时集合的代表就是这条链的最顶端节点（通过查找操作总可以递归找到它）：
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]);
}
查找的复杂度大大降低了！
