在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着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 注意: 输入的二维数组大小在 3 到 1000。 二维数组中的整数在1到N之间，其中N是输入数组的大小。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/redundant-connection 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：dfs 通过深度优先搜索，可以查找是否给定的边有其他的通路，也就是会不会形成环。
class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: N = len(edges) graph = {} for i in range(N): if edges[i][0] not in graph: graph[edges[i][0]] = [] graph[edges[i][0]].append(edges[i][1]) if edges[i][1] not in graph: graph[edges[i][1]] = [] graph[edges[i][1]].append(edges[i][0]) for i in range(N - 1, -1, -1): if self.isLoop(graph, edges[i]): return edges[i] return None def dfs(self,graph, root, end, visited): """ dfs 查找能否从root到达end。 :param graph: :param root: :param visited: :return: """ found = False for neighbor in graph[root]: if neighbor == end: return visited, True if neighbor not in visited: visited.add(neighbor) visited, found = self.dfs(graph, neighbor, end, visited) if found: return visited, True return visited, found def isLoop(self,graph, edge): """ 对于无向边edge，是否存在另一条edge的通路。 :param graph: :param edge: :return: """ start, end = edge[0], edge[1] visited = set() visited.add(end) visited.add(start) for node in graph[start]: if node == end: continue _, found = self.dfs(graph, node, end, visited) if found: return True return False深度优先搜索，对每条边都进行遍历，每条边通过dfs查找是否会形成环，因此是 O(n^2)时间复杂度。
方法二 ：拓扑关系 这里，先把度为 1 的节点找出，然后，不断的删除度为1节点的连接边，在最终节点中，如果边的两个节点度都大于1，则该边为冗余边。
from collections import deque class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: N = len(edges) graph = {} for i in range(N): if edges[i][0] not in graph: graph[edges[i][0]] = [] graph[edges[i][0]].append(edges[i][1]) if edges[i][1] not in graph: graph[edges[i][1]] = [] graph[edges[i][1]].append(edges[i][0]) # 2. 统计度 == 1 indegree = {} queue = deque() for node in graph.keys(): indegree[node] = len(graph[node]) if len(graph[node]) == 1: queue.append(node) while len(queue) > 0: node = queue.popleft() for other_node in graph[node]: indegree[other_node] -= 1 if indegree[other_node] == 1: queue.append(other_node) # 3. 度大于1的节点的任意组合都是可以删除的边 for i in range(N-1, -1, -1): start, end = edges[i][0], edges[i][1] if indegree[start] > 1 and indegree[end] > 1: return edges[i] return None方法三：并查集 首先，并查集用于处理一些不交集（Disjoint Sets）的合并及查询问题。 在这题的无向图中，所有的节点都可以看做有一个公共的根节点。但是，由于存在环的关系，如果在合并边的两个节点时，这两个节点已经属于同一个集合，那么，这条边就是冗余边。 图示的 1-4 边在进行合并前，就已经知道 1 的根节点时4（或者4的父节点是1，看如何定义合并操作），那么，1-4边就是一条冗余边。 并查集主要有三步： （1）初始化各个集合 （2）各个元素查找父节点，（同时进行路径压缩） （3）元素合并成一个集合
class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: def init_parents(N): parents = {} for i in range(1,N+1): parents[i] = i return parents def find_parent(parents, root): """ 查找节点的parent，递归进行路径压缩。 :param parents: :param root: :return: """ if root != parents[root]: parents[root] = find_parent(parents, parents[root]) return parents[root] def union_set(parents, x, y): root_x = find_parent(parents, x) root_y = find_parent(parents, y) if root_x == root_y: return True else: parents[root_x] = root_y return False # 1. 初始化parents parents = init_parents(len(edges)) # 2. 合并路径 for edge in edges: start, end = edge[0], edge[1] # 如果边的两个点的祖先是同一个点，则是冗余连接； if union_set(parents, start, end): return edge return None