LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

LeetCode - 1579. Удаление максимального количества ребер для обеспечения полной проходимости графа

Hard | Python Solution | By Bhupesh Singh Rathore (aka CRUIO)

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

• Тип 1: может быть пройден только Алисой.
• Тип 2: может быть пройден только Бобом.
• Тип 3: может быть пройден как Алисой, так и Бобом.

Учитывая массив edges, где edges[i] = [typei, ui, vi] представляет двунаправленное ребро типа typei между узлами ui и vi, найдите максимальное количество ребер, которое можно удалить, чтобы после удаления ребер граф все еще мог быть полностью пройден Алисой и Бобом. Граф полностью пройден Алисой и Бобом, если, начиная с любого узла, они могут достичь всех остальных узлов.

Верните максимальное количество ребер, которые можно удалить, или верните -1, если Алиса и Боб не могут полностью пройти граф.

Пример 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Пример 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Пример 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Ограничения:

• 1 <= n <= 105
• 1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
• edges[i].length == 3
• 1 <= typei <= 3
• 1 <= ui < vi <= n
• Все кортежи (typei, ui, vi) различны.

РЕШЕНИЕ

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))
        self.count = n

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.parents[root_y] = root_x
            self.count -= 1
            return True
        return False

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

class Solution(object):
    def maxNumEdgesToRemove(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        alice, bob = UnionFind(n), UnionFind(n)
        ans = 0

        # process edges of type 3 for both alice and bob
        for t, u, v in edges:
            if t == 3:
                if not alice.union(u - 1, v - 1) or not bob.union(u - 1, v - 1):
                    ans += 1

        # process edges of type 1 for alice
        for t, u, v in edges:
            if t == 1:
                if not alice.union(u - 1, v - 1):
                    ans += 1

        # process edges of type 2 for bob
        for t, u, v in edges:
            if t == 2:
                if not bob.union(u - 1, v - 1):
                    ans += 1

        # check if all nodes in alice and bob are connected
        if alice.count != 1 or bob.count != 1:
            return -1
        return ans

Счастливого кодирования 😉!!!