## 题目描述：

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.

## 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
``````

## 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:
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)
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]
``````

Pingbacks已关闭。