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大佬， 看到他的思路才逃离了我之前的很复杂的想法。

回到顶部