leetcode如何保证图可完全遍历

这篇文章主要介绍“leetcode如何保证图可完全遍历”，在日常操作中，相信很多人在leetcode如何保证图可完全遍历问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”leetcode如何保证图可完全遍历”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

一、题目内容

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：

• 类型 1：只能由 Alice 遍历。

• 类型 2：只能由 Bob 遍历。

• 类型 3：Alice 和 Bob 都可以遍历。

给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

示例 1：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

示例 2：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

示例 3：

输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

提示：

1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
所有元组 (typei, ui, vi) 互不相同

二、解题思路

维护三种线段的连通关系，线段3一般要保留，毕竟是公用的。

具体思路看代码注释。

三、代码

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: list) -> int:
        uf1 = UnionFind(n)
        uf2 = UnionFind(n)
        uf3 = UnionFind(n)

        count1 = 0  # 线段1的个数
        count2 = 0  # 线段2的个数
        count3 = 0  # 线段3的个数
        redundant_count3 = 0  # 线段3冗余的个数

        for i in range(len(edges)):
            edge_type = edges[i][0]  # 线段种类
            st = edges[i][1] - 1
            ed = edges[i][2] - 1

            # 记录每种线段的个数
            if edge_type == 1:
                count1 += 1
            elif edge_type == 2:
                count2 += 1
            elif edge_type == 3:
                count3 += 1
            else:
                raise ValueError

            # 每种线段进行连通
            if edge_type == 1 or edge_type == 3:
                uf1.Union(st, ed)

            if edge_type == 2 or edge_type == 3:
                uf2.Union(st, ed)

            if edge_type == 3:
                if not uf3.isConnected(st, ed):
                    uf3.Union(st, ed)
                else:
                    # 已经连通说明冗余
                    redundant_count3 += 1
        # 线段3直接连通了所有点
        if uf3.getCount() == 1:
            return count1 + count2 + redundant_count3  # 删除的边可以是线段1+线段2+线段3冗余的个数
        # 线段1和线段2同时连通， 那么都可以走的路不需要删除，也就是线段3不需要删除，但是要删除线段3的冗余
        if uf1.getCount() == 1 and uf2.getCount() == 1:
            return count1 - (uf3.getCount() - 1) + \
                count2 - (uf3.getCount() - 1) + redundant_count3

        return -1


class UnionFind:
    def __init__(self, n):
        self.count = n
        self.root = [0 for _ in range(n)]
        self.size = [0 for _ in range(n)]

        for i in range(n):
            self.root[i] = i
            self.size[i] = i

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

    def isConnected(self, x, y):
        return self.find(x) == self.find(y)

    def getCount(self):
        return self.count

    def Union(self, x, y):
        # 查找x和y的根/父节点
        rx = self.find(x)
        ry = self.find(y)

        # 根/父节点相同， 说明已经连通了
        if rx == ry:
            return  # 直接返回
        if self.size[rx] < self.size[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
        self.count -= 1


if __name__ == '__main__':
    s = Solution()
    n = 4
    edges = [[3, 1, 2],
             [3, 2, 3],
             [1, 1, 3],
             [1, 2, 4],
             [1, 1, 2],
             [2, 3, 4]]

    ans = s.maxNumEdgesToRemove(n, edges)
    print(ans)

到此，关于“leetcode如何保证图可完全遍历”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！