并查表（认老大的区分方式）

一、并查表的用处

一般由于检测图的连通性问题。给你一幅图，和图中两个结点，请问这两个结点是否相连通？或者检测该图中是否有环。当然还可解决其他问题。

二、并查表的构成

由find函数，join函数，以及对应的集合的代表结点数组构成。

像黑社会这种组织，都是老大说了算，老大的手下都是跟着老大做事，可以这么说老大一定程度上是手下的代表，一个老大代表了他所有的手下。将元素都归于集合中，这就是并查表的主要思想。一个人也可以是一个黑社会团体哦
如果对集合概念了解的，可以理解为，将一个个结点（手下）放入到不同的集合（黑社会团体）中，对应的集合的代表结点数组 表示不同的集合（用集合中的一个元素代表该集合）（老大代表了黑社会团体），join函数 的作用是将结点放入到集合中，亦或者将两个集合并操作（两个黑社会黑吃黑，一个黑社会吞并另一个黑社会）。find函数 的作用是给一个结点，找到该结点对应集合的代表结点。（给一个手下找到他所属黑社会的老大）

三、例题剖析

684. 冗余连接
     在本问题中, 树指的是一个连通且无环的无向图。
     输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
     结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
     返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

题目来源：leetcode 684 冗余连接
题目要求可简化为，该无向图中含有一环，请找出该环中一个连接。

解该题的方法有很多，这里只写出使用并查表的解决方案。
举一个例子：
假设输入是：

[[1,4],[3,4],[1,3],[1,2],[4,5]]

可视化的图

很明显，1 - 4 - 3 是一个环，按道理来讲， 返回[1 , 4]，[3, 4] 或者 [1, 3] 都可，而题目中要求 如果有多个答案，则返回二维数组中最后出现的边说明只需要返回[1, 3]。

接下来推断：
我们先创建一个数组 假设索引从1开始，不是0，该数组的索引是指对应的结点，而其值就是结点所属的集合。集合的表示方法用集合元素中的首项来表示该集合。

        # 声明一个数组root_list = [i for i in range(1, len(edges) + 1)]

可以看出一开始每一个结点的结合都只有自己。结点1所属集合只有1一个元素，结点2所属集合只含2一个元素…

find函数的实现

“”“参数：tar 	图中的一个结点的值nums	记录老大数组返回：该结点对应的集合，并返回该集合代表的结点
”“”def find(tar, nums):while tar != nums[tar]:tar = nums[tar]return tar

主函数和join函数的实现：

 for item in edges:# 找到两边结点所属的集合set_1 = find(item[0], root_list)set_2 = find(item[1], root_list)# 如果边开头和边结尾的元素都是同一个集合，说明一定是一个环if set_1 == set_2:return item# 当发现双方所含的集合不一样的时候，选择其中一个集合，另一个集合加入该集合。else:root_list[set_2] = set_1

步骤如下：
root_list：[1, 2, 3, 4, 5]

第一步：
读取[1, 4]
1的集合只含1，4的集合只含4。
发现所属集合不一样，4的集合加入1的集合
所以root_list变化为：[1, 2, 3, 1, 5]

第二步：
读取[3, 4]
3所属集合有3，4所属集合有1，4（用1表示该集合）
发现集合不一样， 4所属的结合加入3的集合中 （4所属的集合的代表是 1，所以数组中第一位的值变为3，说明1集合和3集合合并，那么3集合所包含的元素就有3，1，4）
所以root_list变化为：[3, 2, 3, 1, 5]

第三步：
读取[1, 3]
发现1和3的属于同一个集合，返回该数组[1, 3]为所求。

可能会有疑问，为什么第二步最后的root_list变更是[3, 2, 3, 1, 5]，而不是[3, 2, 3, 3, 5]呢？
1，3，4同属于一个集合中为什么root_list会不一样？当然我们也是想一样的，因为这样的话，find函数就不需要了，直接访问root_list就好了，其索引对应的值就是所属集合的代表。可是我们很难做到，或者说要花费沉重的代价去实现。所以find函数，帮我们节省这些操作。当[3, 2, 3, 1, 5]传入find函数，想找到第四项所属的集合的代表，访问第四项，对应的值1，然后判断1跟索引值4不相同，说明1不是一个集合的代表，然后将1作为索引，访问第一项，第一项的值为3，判断跟索引1不相同，说明3不是一个集合的代表，然后将3作为索引，访问第三项，发现索引值3和其索引对应的值也是3，相同，说明3是一个集合的代表。推出4所属的集合的代表为3。

明白以上操作后，总代码仅仅只是将索引调整了一下，因为索引从0开始：

class Solution(object):def findRedundantConnection(self, edges):""":type edges: List[List[int]]:rtype: List[int]"""def find(tar, nums):while tar != nums[tar - 1]:tar = nums[tar - 1]return tar# 声明一个结点数组root_list = [i for i in range(1, len(edges) + 1)]for item in edges:print("  item 0 :", item[0], "  item 1 :", item[1])set_1 = find(item[0], root_list)set_2 = find(item[1], root_list)print(set_1, set_2)print(root_list)if set_1 == set_2:return item# 进行合并else:root_list[set_2 - 1] = set_1if __name__ == '__main__':test_class = Solution()print(test_class.findRedundantConnection([[1, 4], [3, 4], [1, 3], [1, 2], [4, 5]]))

为什么要使用并查表来解决此题？

假设我们要解决的问题是，给定两个结点，判断该结点是否连通。使用并查集的思路是：将连通第一个结点的所有结点都放入一个集合中，然后看看，另一个结点是否也在该集合中，如果存在就说明连通，不存在就不连通。回到该题，我们将互相连接的元素都放入一个集合中，如果发现有一条边的两头结点都是同一个集合的，说明这条边尚未连接时，这两个结点已经连接起来了，现在再加上这条边，这种情况只有可能是环。

提升

  当发现双方所含的集合不一样的时候，选择其中一个集合，另一个集合加入该集合。

这里有其实应该选择将一个小的集合，加入到一个大的集合。 而不是随机的选择，或者固定左集合往右集合合并，这就是路径压缩算法的核心思想。