[LeetCode]Redundant Connection

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码