题解 | #动物牛的探险之旅#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @param edges int整型二维数组
# @return int整型
#
class Solution:
    def maxRemovableEdges(self, n: int, edges: List[List[int]]) -> int:
        # write code here
        if len(edges) < n - 1:
            return -1
        a, b, c = list(), list(), list()
        for edge in edges:
            if edge[0] == 1:
                a.append([edge[1], edge[2]])
            elif edge[0] == 2:
                b.append([edge[1], edge[2]])
            elif edge[0] == 3:
                c.append([edge[1], edge[2]])

        dsuc = self.DSU(n)
        for edge in c:
            dsuc.union(edge[0], edge[1])

        count = dsuc.count()
        dsua = dsuc.copy()
        dsub = dsuc.copy()

        for edge in a:
            dsua.union(edge[0], edge[1])
        for edge in b:
            dsub.union(edge[0], edge[1])

        if dsua.isConnected() and dsub.isConnected():
            return len(edges) - 2 * (n - 1) + count
        else:
            return -1

    # Disjoint-set data structure
    class DSU:
        def __init__(self, n):
            self.parent = list(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):
            x, y = x-1, y-1
            rootX = self.find(x)
            rootY = self.find(y)
            if rootX != rootY:
                if self.rank[rootX] >= self.rank[rootY]:
                    self.parent[rootY] = rootX
                    self.rank[rootX] += self.rank[rootY] + 1
                    self.rank[rootY] = 0
                else:
                    self.parent[rootX] = rootY
                    self.rank[rootY] += self.rank[rootX] + 1
                    self.rank[rootX] = 0

        def copy(self):
            import copy

            return copy.deepcopy(self)

        def isConnected(self):
            root = self.find(0)
            for i in range(1, len(self.parent)):
                if self.find(i) != root:
                    return False
            return True

        def count(self):
            sum = 0
            for i in range(len(self.rank)):
                sum += self.rank[i]
            return sum

基于类型3的边构建并查集；

分别遍历类型1，2的边，检查并查集是否构成连通图。