23.04.30 Today’s Leetcode

1579. Remove Max Number of Edges to Keep Graph Fully Traversable (hard)

Union and Find Approach : TLE at 80/85

class P:
    def __init__(self, n):
        self.size = n
        self.parent = list(range(n))
        self.parent[0] = 1
        self.rank = [0] * n

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

    def union(self, a, b):
        x, y = self.find(a), self.find(b)
        if x == y:
            return False

        value = min(x, y)
        change = max(x, y)
        for i in range(self.size):
            if self.parent[i] == change:
                self.parent[i] = value
        # print(a, b, self.parent)
        return True

    def check(self):
        return len(set(self.parent)) == 1



class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        p = P(n + 1)
        q = P(n + 1)
        res = 0

        for t, a, b in edges:
            if t == 3:
                x = p.union(a, b)
                y = q.union(a, b)
                if x or y:
                    res += 1

        for t, a, b in edges:
            tar = p if t == 1 else q
            val = tar.union(a, b)
            if val:
                res += 1

            
        # print(p.parent)
        # print(q.parent)
        return len(edges) - res if p.check() and q.check() else -1

Another Union and Find Approach

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        xset, yset = self.find(x), self.find(y)
        if xset != yset:
            if self.rank[xset] < self.rank[yset]:
                self.parent[xset] = yset
            elif self.rank[xset] > self.rank[yset]:
                self.parent[yset] = xset
            else:
                self.parent[xset] = yset
                self.rank[yset] += 1
            return True
        return False

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        edges.sort(reverse=True)
        dsu_alice = DSU(n+1)
        dsu_bob = DSU(n+1)
        removed_edge = 0
        alice_edges, bob_edges = 0, 0
        for edge in edges:
            if edge[0] == 3:
                if dsu_alice.union(edge[1], edge[2]):
                    dsu_bob.union(edge[1], edge[2])
                    alice_edges += 1
                    bob_edges += 1
                else:
                    removed_edge += 1
            elif edge[0] == 2:
                if dsu_bob.union(edge[1], edge[2]):
                    bob_edges += 1
                else:
                    removed_edge += 1
            else:
                if dsu_alice.union(edge[1], edge[2]):
                    alice_edges += 1
                else:
                    removed_edge += 1
        return removed_edge if bob_edges == n - 1 == alice_edges else -1

396. Rotate Function (medium)

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        total = sum(nums)
        temp = 0
        index = n - 1
        for i, v in enumerate(nums):
            temp += i * v

        res = -math.inf
        for i in range(n):
            res = max(res, temp)
            temp += total
            temp -= n * nums[index]
            index -= 1

        return res