singularity

singularity 🔎

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

O(N+M) / amortized

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

    def union(self, a, b):
        pa, pb = self.find(a - 1), self.find(b - 1)
        if pa == pb:
            return False
        self.p[pa] = pb
        self.n -= 1
        return True

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


class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        ufa, ufb = UnionFind(n), UnionFind(n)
        ans = 0
        for t, u, v in edges:
            if t == 3:
                if ufa.union(u, v):
                    ufb.union(u, v)
                else:
                    ans += 1
        ans += sum(
            (t == 1 and not ufa.union(u, v)) or (t == 2 and not ufb.union(u, v))
            for t, u, v in edges
        )

        return ans if ufa.n == 1 and ufb.n == 1 else -1