题目描述：
LeetCode 684. Redundant Connection
We are given a "tree" in the form of a 2D-array, with distinct values for each node.
In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree.
We can remove exactly one redundant pair in this "tree" to make the result a tree.
You need to find and output such a pair. If there are multiple answers for this question, output the one appearing last in the 2D-array. There is always at least one answer.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: Original tree will be like this: 1 / \ 2 - 3
Example 2:
Input: [[1,2], [1,3], [3,1]] Output: [3,1] Explanation: Original tree will be like this: 1 / \\ 2 3
Note:
- The size of the input 2D-array will be between 1 and 1000.
- Every integer represented in the 2D-array will be between 1 and 2000.
题目大意：
给定二维数组edges表示的一棵“树”。二维数组的每个元素[u, v]表示v是u的孩子。
树中多余一条边，在edges中恰好移除一条边，可以使得剩余边组成一棵没有环的树。
求移除的边，若存在多种答案，移除在edges中顺序靠后的那一条。
解题思路：
解法I 并查集（Union Find Set）
Python代码：
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
p = list(range(max(reduce(operator.add, edges)) + 1))
def find(a):
while p[a] != a: a = p[a]
return a
for s, t in edges:
ps, pt = find(s), find(t)
if ps == pt: return [s, t]
p[ps] = pt
解法II 拓扑排序（Topological Sort）
利用数组degree记录各顶点的度。
利用数组neighbor记录各顶点的邻接顶点。
从度为1的节点出发进行拓扑排序，剩余边中在edges中排最后的那条即为答案。
Python代码：
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
neighbor = collections.defaultdict(set)
degree = collections.defaultdict(int)
for s, t in edges:
neighbor[s].add(t)
neighbor[t].add(s)
degree[s] += 1
degree[t] += 1
degOnes = [k for k, v in degree.iteritems() if v == 1]
while degOnes:
ndegOnes = []
for s in degOnes:
deletes = set()
for t in neighbor[s]:
degree[t] -= 1
if degree[t] == 1: ndegOnes.append(t)
deletes.add(t)
for t in deletes: neighbor[t].remove(s)
del degree[s]
del neighbor[s]
degOnes = ndegOnes
for s, t in edges[::-1]:
if min(degree[s], degree[t]) > 1: return [s, t]
本文链接：http://bookshadow.com/weblog/2017/09/24/leetcode-redundant-connection/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
