【数据结构】看完必会的并查集入门攻略2.0
本文是前文的升级版本，在前文的基础上，增加了更详细的讲解，将实现过程分步描述，并且将前文的python实现改成了cpp的实现。
“并查集”是一种思路巧妙，代码很短的数据结构，也因此常常在算法题或者面试中出现。下面我们以一个模板题目作为示例，详细描述并查集的基本原理及使用。
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
有n个数，编号1~n。现在有两个操作：
M（merge）。合并两个数到一个集合中，如M a b，则表示a和b合并到一个集合。
Q（query）。查询两个数是否在一个集合，如Q a b，查询a和b是否在一个集合当中。
如果对于两个数，“每个数初始都自己占用一个集合，那么合并两个数就将其中一个数的所属集合变为另外一个”，但是这样做，“在查询的时候则必须遍历两个数的所属集合”，所以单次查询的时间复杂度是O(n)。
“并查集”，从名字中也可以看出来，“这是一个专门负责 合并与查询 的数据结构”。
在并查集中，使用多叉树的形式来维护所有的集合。“使用根节点的编号来作为整个集合的编号，每个节点存储它的父节点，根节点存储它自己”。用p[x]表示x的父节点编号。
在这里，我们需要明确“集合与节点是包含关系”。
“用集合的根节点编号表示一个集合”。比如，也就是初始化之后，1号节点因为“它的节点编号和父节点编号相同”，因此它就是一个集合的根节点，因为它的节点编号是1，所以该集合的编号也是1。
所以，后文所说的"集合1"，就是代表“以1号节点为根节点的整个集合”。在上图中，这个集合包含七个元素（未合并前）。
为了方便后续的并和查的操作，我们在初始化阶段让“每个节点都属于一个单独的集合”，实现上就是“节点编号”等于“它的父节点编号”，如：节点1的父节点也是1。
“合并两个节点a和b”。直接将一个节点的所在集合 指向 另外一个节点的所在集合。
如下图，我们把“节点2”合并到“节点1”，既，“集合2的父节点编号 变成 集合1的节点编号”。
找到元素x属于哪个集合（也就是find函数）。我们“沿着x的父节点一直向上搜索，直到找到x的最终根节点”。
根据“初始化的规则”，我们可以直观的知道，判断“一个点是不是最终根节点”，实际上就是在看“一个点的编号 是否等于 它的父节点的编号”。用代码表示就是(p[i] == i)。
经过合并之后，“节点的所属集合就会改变”。
如图中“节点2”的所属集合本来是它自己，但是我们合并之后，把整个“集合2”合并到“集合1”上，所表现出来的现象就是“原本节点2的父节点是它自己(2) 表示它是集合2的最终根节点”，合并之后“节点2的父节点变成了节点1，它的父节点不再是它自己，所以它也再属于集合2”。
那么，如何找到“节点2”合并后属于哪个“集合”呢？
我们只要“沿着它的父节点向上找，直到找到最终根节点”（参考概念图中天蓝色的文字描述部分）。
我们发现在“查找”这个操作上，我们要沿着父节点一点点的向上查找，直到找到最终根节点为止。
比如，找到节点7的所属集合，需要查找四次。这个“查找次数和树的高度是成正比例的”，也就是说所需要的时间复杂度是log(n)级别的。
而有一种优化方式，可以把这个复杂度优化到O(1)级别。“在合并的时候，我们直接让所有的节点的父节点都指向所在集合的根节点”。
这种优化方式的好处也很明显，“只需要向上找一次就可以知道某个元素属于哪个集合”。
实现上，我们可以在“查找”操作的过程中，把“对于 非根节点 把它 指向 它所在集合的根节点”。
考虑这样一个问题：“求某个集合的节点数量”应该怎么办？
只需要“多开一个数组size[]来记录每个集合中的节点数量”。
初始化size[]，每个集合只有一个节点，既，根节点自己。只有集合合并的时候才会影响到一个集合的节点数量。所以在“合并”的时候，我们只要“把两个集合的节点数量加一起就可以了”。
比如：p[x]=y该操作将x合并到集合y中，那么显然集合数量的变化就是size[y] += size[x]。
我们把上面分析的所有代码总结一下，就可以完成本题。