03并查集
# 03 并查集
并查集（union-find, 或 disjoint set）可以动态地连通两个点，并且可以非常快速地判断两个 点是否连通。假设存在 n 个节点，我们先将所有节点的父亲标为自己；每次要连接节点 i 和 j 时， 我们可以将 i 的父亲标为 j；每次要查询两个节点是否相连时，我们可以查找 i 和 j 的祖先是否最 终为同一个人。
# 684 冗余连接 (opens new window)
在无向图找出一条边，移除它之后该图能够成为一棵树（即无向无环图）。如果有多个解，返 回在原数组中位置最靠后的那条边。
输入是一个二维数组，表示所有的边（对应的两个节点）；输出是一个一维数组，表示需要移除的边（对应的两个节点）。
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
解析：
# 685 冗余连接 II (opens new window)
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]
解析：
# 399 除法求值 (opens new window)
给定一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释： 条件：a / b = 2.0, b / c = 3.0 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
解析：
# 1631 最小体力消耗路径 (opens new window)
给定一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
一开始在最左上角的格子 (0, 0) ，且希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
每次可以往 上，下，左，右 四个方向之一移动，想要找到耗费体力最小的一条路径。
一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。
请返回从左上角走到右下角的最小体力消耗值 。
输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
解析：