冗余连接II

题目链接

题目原文

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

输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

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

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

示例 1:
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
   1
  /   \
 v    v
2-->3

示例 2:
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
        ^        |
        |        v
        4 <- 3

题目解析

一棵有N个节点的树,它的边为N-1条。题目所给的边有N条,存在一条附加边。多了这条边之后有两种情况:

  • 附加边指向根节点,由于所有节点都有父节点,且是根节点的后继,所以图中一定存在环路。
  • 附加边指向非根节点,则恰好有一个节点存在两个父节点,此时图中可能有环路,也可能没有。

本题的目标就是找到这条附加边,我们需要遍历图中的所有边构建出一个树,在此过程中找到与有根树条件冲突的边。

解题方法

解题思路

具体做法如下,使用数组parent记录每个节点的父节点,初始时对于每个节点1N1 \leq N都有parent[i]=iparent[i]=i,另外创建并查集,初始时并查集中的每个节点都是一个连通分支,该连通分支的根节点就是该节点本身。

当访问到边[u,v]时,进行如下操作:

  • 如果此时已经有parent[v]vparent[v]\neq v,说明v有两个父节点,将当前边[u,v]标记为导致冲突的边。
  • 否则,令parent[v]=uparent[v] = u,然后在并查集中分别找到u和v的祖先,如果祖先相同,说明这条边导致环路出现,将当前的边[u,v]记为导致环路出现的边,如果祖先不同,则在并查集中将u和v进行合并。

如果没有导致冲突的边,说明附加边一定导致环路出现,而且是在环路中的最后一条被访问到的边,因此附加的边即为导致环路出现的边。

如果有导致冲突的边,记这条边为[u,v],则有两条边指向v,另一条边为[parent[v],v],需要通过判断是否有导致环路的边决定哪条是附加边。

  • 如果有导致环路的边,则附加边不可能是[u,v](因为[u,v]已经被记为导致冲突的边,不可能被记为导致环路的边),因此附加边是[parent[v],v]

  • 如果没有导致环路的边,则附加的边是后被访问到的指向v的边,附加边是[u,v]

所有结果分析

  1. 无冲突,有环,返回环路中最后访问的边,即成环边。
    例子[[1,2],[2,3],[3,4],[4,1]],不存在导致冲突的节点,但是[4,1]使得图存在环路,因此附加边为[4,1]

    无冲突,有环无冲突,有环

  2. 有冲突,无环,直接返回冲突边
    例子[[1,2],[1,3],[2,3]],此时,[2,3],会使得3有两个父节点,产生冲突,但不产生环

    有冲突,无环有冲突,无环

  3. 有冲突,有环:这种情况下要保留冲突边,因为环的影响优先于冲突,如果去掉冲突边,仍可能存在环,去掉环中会导致冲突的边[parent[v],[v]]
    例子[[2,1],[3,1],[1,4],[4,2]],此时[3,1]产生冲突,[4,2]产生环,保留冲突边[3,1],通过找到1的父节点,找到造成环的边[2,1]

    有冲突,有环有冲突,有环

# 并查集,用于记录环
class UnionFind:
    def __init__(self, n):
        self.ancestor = list(range(n))
    
    def union(self, index1: int, index2: int):
        self.ancestor[self.find(index1)] = self.find(index2)
    
    def find(self, index: int) -> int:
        if self.ancestor[index] != index:
            self.ancestor[index] = self.find(self.ancestor[index])
        return self.ancestor[index]

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        nodesCount = len(edges)
        # 初始化并查集,每个节点都是一个连通分支,该连通分支的根节点就是该节点本身。
        uf = UnionFind(nodesCount + 1)
        parent = list(range(nodesCount + 1))
        conflict = -1
        cycle = -1
        for i, (node1, node2) in enumerate(edges):
            # 导致冲突的边
            if parent[node2] != node2:
                # 记录该边的索引
                conflict = i
            else:
                # 更新parent数组
                parent[node2] = node1
                # [u,v]查询的父节点
                if uf.find(node1) == uf.find(node2):
                    cycle = i
                else:
                    uf.union(node1, node2)

        #无冲突,有环,直接返回成环边
        if conflict < 0:
            return [edges[cycle][0], edges[cycle][1]]
        else:
            #有冲突
            conflictEdge = edges[conflict]
            #有冲突,有环,返回冲突边[u,v]对应的[parent[v],v]
            if cycle >= 0:
                return [parent[conflictEdge[1]], conflictEdge[1]]
            #有冲突,无环,返回冲突边
            else:
                return [conflictEdge[0], conflictEdge[1]]

参考

https://leetcode-cn.com/problems/redundant-connection-ii/solution/rong-yu-lian-jie-ii-by-leetcode-solution/
https://leetcode-cn.com/problems/redundant-connection-ii/solution/guan-fang-ti-jie-fu-zhu-yue-du-qing-xi-dai-tu-by-c/