685. 冗余连接 II

#python #leetcode #union-find #directed-graph

题目描述

关联：

• https://leetcode.cn/problems/redundant-connection-ii/description/
• https://leetcode.cn/problems/redundant-connection/description （684）

题目描述

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges。每个元素是一对 [u_i, v_i]，用以表示 有向 图中连接顶点 u_i 和顶点 v_i 的边，其中 u_i 是 v_i 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

本题和 684. 冗余连接 的区别在于，本题的输入中为有向边。

解题思路

本题是 684. 冗余连接 的扩展版本，区别在于本题的输入是有向图。

我们需要找到一条边，使得删除这条边后，剩下的图是一个有根树。

树和图的区别在于，树不会有环，也不会存在一个节点有两个父节点。

因此可以分为以下几种情况：

1. 没有节点有两个父节点：这种情况下，破坏了树的结构的就是环，找到这个环，并删除环中的任意一条边即可。

2. 有一个节点有两个父节点：这种情况下，删除其中一条边（称为冲突边），如果删除后图中没有环，则这条边就是答案；如果删除后图中还有环，则另一条边就是答案。

我们仍然使用并查集（Union-Find）来检测环，并结合额外的逻辑来处理有两个父节点（即存在冲突边）的情况

完整题解

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

class Solution:
    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        uf = UnionFind(n + 1)
        parent = list(range(n + 1))  # 初始化父节点数组
        conflict = -1  # 记录冲突边的索引（破坏树的条件 1）
        cycle = -1  # 记录成环边的索引（破坏树的条件 2）

        for i, (u, v) in enumerate(edges):
            # 存在冲突边的情况
            if parent[v] != v:
                conflict = i
            else:
                parent[v] = u
                if not uf.union(u, v):  # 存在成环的情况
                    cycle = i

        if conflict < 0:
            # 没有冲突边，返回成环边
            return edges[cycle]
        else:
            conflict_edge = edges[conflict]
            if cycle >= 0:
                # 有冲突边且有成环边，返回冲突边的另一条边
                return [parent[conflict_edge[1]], conflict_edge[1]]
            else:
                # 只有冲突边，返回冲突边
                return conflict_edge

复杂度分析

本题所需考虑的时间空间复杂度和 684. 冗余连接 相同，不再赘述。

评论