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

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序定制開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了黑龍江免費(fèi)建站歡迎大家使用！

一、題目?jī)?nèi)容

Alice 和 Bob 共有一個(gè)無(wú)向圖，其中包含 n 個(gè)節(jié)點(diǎn)和 3  種類(lèi)型的邊：

• 類(lèi)型 1：只能由 Alice 遍歷。

• 類(lèi)型 2：只能由 Bob 遍歷。

• 類(lèi)型 3：Alice 和 Bob 都可以遍歷。

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

返回可以刪除的最大邊數(shù)，如果 Alice 和 Bob 無(wú)法完全遍歷圖，則返回 -1 。

示例 1：

輸入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
輸出：2
解釋?zhuān)喝绻麆h除 [1,1,2] 和 [1,1,3] 這兩條邊，Alice 和 Bob 仍然可以完全遍歷這個(gè)圖。再刪除任何其他的邊都無(wú)法保證圖可以完全遍歷。所以可以刪除的最大邊數(shù)是 2 。

示例 2：

輸入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
輸出：0
解釋?zhuān)鹤⒁猓瑒h除任何一條邊都會(huì)使 Alice 和 Bob 無(wú)法完全遍歷這個(gè)圖。

示例 3：

輸入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
輸出：-1
解釋?zhuān)涸诋?dāng)前圖中，Alice 無(wú)法從其他節(jié)點(diǎn)到達(dá)節(jié)點(diǎn) 4 。類(lèi)似地，Bob 也不能達(dá)到節(jié)點(diǎn) 1 。因此，圖無(wú)法完全遍歷。

提示：

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) 互不相同

二、解題思路

維護(hù)三種線(xiàn)段的連通關(guān)系，線(xiàn)段3一般要保留，畢竟是公用的。

具體思路看代碼注釋。

三、代碼

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

        count1 = 0  # 線(xiàn)段1的個(gè)數(shù)
        count2 = 0  # 線(xiàn)段2的個(gè)數(shù)
        count3 = 0  # 線(xiàn)段3的個(gè)數(shù)
        redundant_count3 = 0  # 線(xiàn)段3冗余的個(gè)數(shù)

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

            # 記錄每種線(xiàn)段的個(gè)數(shù)
            if edge_type == 1:
                count1 += 1
            elif edge_type == 2:
                count2 += 1
            elif edge_type == 3:
                count3 += 1
            else:
                raise ValueError

            # 每種線(xiàn)段進(jìn)行連通
            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)連通說(shuō)明冗余
                    redundant_count3 += 1
        # 線(xiàn)段3直接連通了所有點(diǎn)
        if uf3.getCount() == 1:
            return count1 + count2 + redundant_count3  # 刪除的邊可以是線(xiàn)段1+線(xiàn)段2+線(xiàn)段3冗余的個(gè)數(shù)
        # 線(xiàn)段1和線(xiàn)段2同時(shí)連通， 那么都可以走的路不需要?jiǎng)h除，也就是線(xiàn)段3不需要?jiǎng)h除，但是要?jiǎng)h除線(xiàn)段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é)點(diǎn)
        rx = self.find(x)
        ry = self.find(y)

        # 根/父節(jié)點(diǎn)相同， 說(shuō)明已經(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)

到此，關(guān)于“l(fā)eetcode如何保證圖可完全遍歷”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！