并查集适用来高效地处理不相交集合（disjoint sets）的合并及查询问题。尤其是出现判断数据的相交情况时，尤其的高效。例如LeetCode的684题：无向图寻找闭环。原题如下：
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v]，满足u < v，表示连接顶点u和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边[u, v] 应满足相同的格式u < v。
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
对于此题，可以通过遍历每一条边的两个端点，寻找两个端点的祖父节点来查看他们是否为同一集合，如果是同一集合，说明已经形成了闭环。以
[[1,2], [2,3], [3,4], [1,4], [1,5]]
5 - 1 - 2
| |
4 - 3
为例。首先初始化每个节点的父亲节点为自己，此时有parents=[0,1,2,3,4,5]，其中parents[i]=i表示第i个节点的父亲节点就是自己(0节点无意义)。遍历[1,2]，此时1,2的父节点为1,2，属于不同的祖父节点。对节点进行合并，将2节点的父亲节点更改为1。再遍历[2,3]，此时2，3的父亲节点不同，同样进行合并，那么3的父亲节点变为1（变成2也可以，但是为了高效的查询，需要对路径进行压缩，使得3直接变成1的子节点）。再遍历[3,4]，此时吧4直接作为1的子节点。再遍历[1,4]，此时发现1,4的父亲节点都是一样的，都为1.那么说明出现了闭环，即返回[1,4]。
并查集-Find(寻找)
作为每个节点必备的操作，寻找父节点是非常重要的操作。可以采用递归方式和非递归方式进行。
# 在没有找到祖父节点的前提下，一直往前寻找。祖父节点的特点是自己的父亲节点就是自己
def find(parents:List[int],x):
if x!=parents[x]:
find(parents,parents[x])
return parents[x]
并查集-Join(压缩)
路径压缩的最终目的是为了高效的查询，做法是将每个子节点直接接在祖父节点下，如果不进行路径压缩，那么在查询时需要不断地向上寻找祖父节点。
1->4->9->6->3->7
路径压缩：
|->4
|->9
1-|->6
|->3
|->7
每次查询之后直接改变当前节点的父亲节点，如上面的直接把4,9,6,3,7变为1的子节点。
每次查找向上寻找祖父节点之后，将该节点直接连接到祖父节点，实现如下：
def join(parents,x):
parents[x]=find(parents,x)
