并查集实践

代码实践（当节点指向自己时，为根节点）

p[1] != 4 所以x作为4往下递归。发现p[4] != 3 ，x作为3再往下递归。p[3] == 3 ，此时符合返回x=3 。 x=3先返回给p[4] , 在返回给p[2],最终2，4都指向3.

按高度合并 logn

操作：合并2和0号点这两棵树。1我们先向上查询是不是同一个结点

2，如果不是，才使一个根结点指向另一个更结点

指向时，如果让矮的指向高的，那么树的高度就不会变，时间查询就会降低。

按大小合并：因为路径压缩之后，导致所有树都指向根结点，都只有两层。logn

给一个size数组，记录包含自身结点的所有结点，比较然后合并

我们发现，仅仅只需要根节点的高度和个数，不需要每个结点都开辟一个数组存储高度和个数。

所以我们可以讲p[4]（根节点）的高度和个数改为负值，可以避免与其他节点重复。

负数代码实现

按高度合并，负数自减1相当于高度加1

按大小合并，先叠加后赋值。因为先赋值的话，p[root]的大小会被覆盖。