当前位置：首页 > article >正文

685. 冗余连接 II

article 2024/10/28 22:35:36

力扣刷题记录

并查集有向图

685. 冗余连接 II

思路

对于这道困难题，并没有思路
从昨天的无向图变为今天的有向图，题目从中等升级到了困难

因此需要同时记录上一级连接的节点和使用并查集
树中所有入度除了一个为0 其它的为1
记录上一级的节点是为了判断是否存在冲突的边，即这个点存在两个入度
因此记录这一条冲突的边

否则判断这条边是否会形成环路
通过加入并查集进行判断成环了记录下来

最后如果没有冲突的边 跟昨天一样返回最后标记成环的边即可

否则

有冲突的边 假设为 [u, v] 此时肯定得返回 [u, v] 或者 [parents[v], v] 中的一条（为了保证入度正常）

没有成环的边 返回冲突的边 [u, v]即可

如果既有冲突的边，也有成环的边，成环的边不可能是[u, v] 因为已经被标记了，不会进入成环的监测再进行标记，因此直接返回另外一条边 [parents[v], v] 即可（不一定返回最后标记的成环那一条边，因为一个环中的另外一条边[parents[v], v] 需要返回才能同时去掉环和存在入度异常的点）

代码

func find(ancestor []int, x int) int{
    if ancestor[x] != x{
        ancestor[x] = find(ancestor, ancestor[x])  // 路径压缩  只保留最根的节点
        // return find(ancestor, ancestor[x]) // 不进行路径压缩
    }
    return ancestor[x]
}

func findRedundantDirectedConnection(edges [][]int) []int {

    var parents []int = make([]int, len(edges) + 1) // 记录上一级父节点
    var ancestor []int = make([]int, len(edges) + 1) // 记录最上面的祖先节点   并查集
    for i := 0; i < len(edges) + 1 ; i++{
        parents[i] = i
        ancestor[i] = i
    }

    conflict := -1
    cycle := -1
    for i, edge := range edges{
        from := edge[0]
        to := edge[1]

        if parents[to] != to{
            // 该点 已经在一条边中加入了 已经有一个入度了
            conflict = i
        }else{
            parents[to] = from

            m := find(ancestor, from)
            n := find(ancestor, to)

            if m == n{
                // 成环了
                cycle = i
            }else{
                ancestor[m] = n
            }
        }
    }

    if conflict < 0{
        // 和昨天的一样，返回成环的边即可
        return edges[cycle]
    }else{
        to := edges[conflict][1]
        if cycle >= 0{
            var res []int = make([]int, 2)
            res[0] = parents[to]
            res[1] = to
            return res
        }else{
        	// 没有成环的 返回 冲突的边即可
            return edges[conflict]
        }
    }
}