这是Leetcode的原题目
""" In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed. The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v. Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v. Example 1: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3 Example 2: Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 4 - 3 Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array. Update (2017-09-26): We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenience caused. """
通读题目，以及观察样例，我们其实很容易发现这题的根本问题——查找一个无向图中是否含有环，若存在环，那么可以删除一条边使图依旧连通，那么这个时候，对于无向图这个结构来说，我们用并查集的方法来实现，就很快能解决问题了。那什么是并查集？这里引用维基百科的解释：
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
因此，我们可以得出并查集算法最重要的两个方法：find方法和union（merge）方法，find方法用于查找某个元素的老大（可能是自己），union（merge）用于解决两个元素的从属问题，就是帮小弟认老大；并查集算法的实现，可能还需要前期以一些数据工作的准备，将所有元素去重存储到一个array或者list中，并初始化他们的老大为他们自己对应的数组下标，接着，用一个循环去遍历原始信息，在遍历中调用union方法从而首先元素的归属问题。
接着，我们在回到本题，如果是判断一个无向图中是否有环，我们只需要判断两个元素的老大是不是同一个即可，如果是用一个老大，我们就把这条边放到一个list当中，当遍历结束，list里面的元素就是本题答案。
这里贴上本题leetcode的AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution(object):
def __init__(self):
self.a, self.ans = {}, []
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
cnt = 0
for i in edges:
for j in i:
if j not in self.a.keys():
self.a[j] = cnt
cnt += 1
self.temp = list(range(len(self.a)))
[self.union(self.a[i], self.a[j]) for i, j in edges]
return [key for key in self.a.keys() if self.a[key] == self.ans[0][0] or self.a[key] == self.ans[0][1]]
def union(self, i, j):
f1, f2 = self.find(i), self.find(j)
if f1 == f2:
self.ans.append([i, j])
else:
self.temp[f1] = f2
def find(self, i):
while i != self.temp[i]:
i = self.temp[i]
return i
if __name__ == '__main__':
s = Solution()
print s.findRedundantConnection([[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]]