题目要求可简化为，该无向图中含有一环，请找出该环中一个连接 。
解该题的方法有很多，这里只写出使用并查表的解决方案 。
举一个例子：
假设输入是：
[[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
步骤如下：
：[1, 2, 3, 4, 5]
第一步：
读取[1, 4]
1的集合只含1，4的集合只含4 。
发现所属集合不一样，4的集合加入1的集合
所以变化为：[1, 2, 3, 1, 5]
第二步：
读取[3, 4]
3所属集合有3，4所属集合有1，4（用1表示该集合）
文章插图
发现集合不一样，4所属的结合加入3的集合中 （4所属的集合的代表是 1，所以数组中第一位的值变为3，说明1集合和3集合合并，那么3集合所包含的元素就有3，1，4）
所以变化为：[3, 2, 3, 1, 5]
第三步：
读取[1, 3]
发现1和3的属于同一个集合，返回该数组[1, 3]为所求 。
可能会有疑问，为什么第二步最后的变更是[3, 2, 3, 1, 5]，而不是[3, 2, 3, 3, 5]呢？
1，3，4同属于一个集合中为什么会不一样？当然我们也是想一样的，因为这样的话，find函数就不需要了，直接访问就好了，其索引对应的值就是所属集合的代表 。可是我们很难做到，或者说要花费沉重的代价去实现 。所以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]]))
- 中国最大的花海排名？
- 法国科学家大脑计算机,重磅！我国科学家成功研制全球神经元规模最大的类脑计算机
- 客观题和主观题怎样区分 客观题和主观题怎样区别
- 甘肃辣椒种植基地有哪些？
- pu皮vs真皮哪个好 pu皮和真皮容易区分吗
- 6kw用多大的空气开关
- 220v家用漏电保护器用多大的
- 如何压缩图片大小？图片太大这样压缩
- 文艺复兴时期三位伟大的悲剧是
- 城南客运站