leetcode如何保證圖可完全遍歷

這篇文章主要介紹“l(fā)eetcode如何保證圖可完全遍歷”，在日常操作中，相信很多人在leetcode如何保證圖可完全遍歷問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”leetcode如何保證圖可完全遍歷”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

一、題目內(nèi)容

Alice 和 Bob 共有一個無向圖，其中包含 n 個節(jié)點和 3  種類型的邊：

• 類型 1：只能由 Alice 遍歷。

• 類型 2：只能由 Bob 遍歷。

• 類型 3：Alice 和 Bob 都可以遍歷。

給你一個數(shù)組 edges ，其中 edges[i] = [typei, ui, vi] 表示節(jié)點 ui 和 vi 之間存在類型為 typei 的雙向邊。請你在保證圖仍能夠被 Alice和 Bob 完全遍歷的前提下，找出可以刪除的最大邊數(shù)。如果從任何節(jié)點開始，Alice 和 Bob 都可以到達所有其他節(jié)點，則認為圖是可以完全遍歷的。

返回可以刪除的最大邊數(shù)，如果 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 仍然可以完全遍歷這個圖。再刪除任何其他的邊都無法保證圖可以完全遍歷。所以可以刪除的最大邊數(shù)是 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 無法從其他節(jié)點到達節(jié)點 4 。類似地，Bob 也不能達到節(jié)點 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的個數(shù)
        count2 = 0  # 線段2的個數(shù)
        count3 = 0  # 線段3的個數(shù)
        redundant_count3 = 0  # 線段3冗余的個數(shù)

        for i in range(len(edges)):
            edge_type = edges[i][0]  # 線段種類
            st = edges[i][1] - 1
            ed = edges[i][2] - 1

            # 記錄每種線段的個數(shù)
            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:
                    # 已經(jīng)連通說明冗余
                    redundant_count3 += 1
        # 線段3直接連通了所有點
        if uf3.getCount() == 1:
            return count1 + count2 + redundant_count3  # 刪除的邊可以是線段1+線段2+線段3冗余的個數(shù)
        # 線段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的根/父節(jié)點
        rx = self.find(x)
        ry = self.find(y)

        # 根/父節(jié)點相同， 說明已經(jīng)連通了
        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)

到此，關于“l(fā)eetcode如何保證圖可完全遍歷”的學習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>