Skip to content

685 Redundant Connection II

685. Redundant Connection II

题目: https://leetcode.com/problems/redundant-connection-ii/

难度 : Hard

我们先定义一下,每条边的第一个点是parent,第二个点是child,例如 2 -> 1 中 node 2 就是 parent,而 node 1 就是 child

明确这个之后,我们要知道图中有一条边是 invalid 的,去除它之后整个图就变成了一棵树,那么什么情况下一个边会导致树变成图呢:

  1. 如果一个child 在此之前已经有过一个parent了,那么意味着它有两个parent,这在树中肯定是不合法的。 在代码中体现为node_parent[child] != child,这说明在碰到此时的parent之前我们就已经更新过node_parent[child]了,即child之前已经有一个parent了
  2. 如果一个child 的 parent 的 parent(或者一直往上找) 就是 child 本身,那么这意味着有环,这在树中也肯定是不合法的。 在代码中体现为find(node_parents, parent) == child, 这说明child的parent的parent或以上就是child本身,即有环。 例如 1 --> 2 --> 1或者1 --> 2 --> 3 --> 1

因此我们可以定义一个列表 node_parent,在最开始的时候,此列表的 index 和 value 一一相等。

然后我们对edges进行第一轮遍历(正序遍历),并且用count来计数不合法的边: - 如果只找到一条不合法的边,那么直接返回它即可 - 如果有超过一条不合法的边,那么我们就进行第二轮遍历(逆序遍历),返回碰到的第一条不合法的边, 这里是为了节约时间,因为如题意我们要返回的是最后一条出现的边,那么我们逆序就更省时间嘛

class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """

        def find(node_parent, parent):
            return parent if node_parent[parent] == parent else find(node_parent, node_parent[parent])

        n, count = len(edges), 0 # 用 count 来计数不合法的边
        node_parent = [i for i in range(n+1)]
        res = [0, 0]

        # 第一轮查找不合法的边 (正序)
        for i in range(n):
            parent, child = edges[i][0], edges[i][1]
            if node_parent[child] != child or find(node_parent, parent) == child:
                res = edges[i]
                count += 1
            else:
                node_parent[child] = parent
        if count == 1: # 如果只有一条不合法的边,直接返回
            return res 

        # 重置 node_parent 并开始第二轮查找 (逆序)
        node_parent = [i for i in range(n+1)]
        for i in range(n-1, -1, -1):
            parent, child = edges[i][0], edges[i][1]
            if node_parent[child] != child or find(node_parent, parent) == child:
                return edges[i]
            else:
                node_parent[child] = parent
        return res

这道题感谢xyzxuyizhen大佬, 看到他的思路才逃离了我之前的很复杂的想法。



回到顶部