目录

• 题目截图
• 题目分析
• ac code
• 总结

题目截图

题目分析

• 从删除比较难，考虑增加
• 增加的过程中无用的边就可以删除
• 考虑alice和bob各自的联通分量
• 最后希望都是1，一开始都是n
• 如果将两个独立的联通分量连起来了，那么连通分量个数减1
• 这里很明显就是用并查集了
• 公共边的贡献最大，先考虑；独立的边后考虑
• alice和bob各自维护一个并查集
• 如果当前的边确实可以达到合并两个联通分量的目的，加进来；否则ans += 1
• 最后看a和b维护的并查集的连通分量个数是否都是1即可
• 需要在并查集的merge中判断xy是否已经同属一个联通分量，返回True或者False

ac code

class UnionFind:def __init__(self, n):self.parent = list(range(n))self.cnt = n # 连通块个数def find(self, a):acopy = awhile a != self.parent[a]:a = self.parent[a]while acopy != a:self.parent[acopy], acopy = a, self.parent[acopy]return adef merge(self, a, b):# 这是一个无用的合并if self.find(b) == self.find(a):return False# 这是一个有用的合并self.parent[self.find(b)] = self.find(a)self.cnt -= 1return Trueclass Solution:def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:# edges预处理为[0, n - 1]for i in range(len(edges)):edges[i][1] -= 1edges[i][2] -= 1# 加入两个并查集ufa, ufb = UnionFind(n), UnionFind(n)# 记录删除无用边的总个数ans = 0 # 先看公共边for t, u, v in edges:if t == 3:flag1 = ufa.merge(u, v)flag2 = ufb.merge(u, v)# 都没有用才不要这个公共边# 否则它的贡献至少是独有边if not flag1 and not flag2:ans += 1else:pass# 再看单独边for t, u, v in edges:if t == 1:if not ufa.merge(u, v):ans += 1elif t == 2:if not ufb.merge(u, v):ans += 1#print(ufa.parent)#print(ufb.parent)if ufa.cnt != 1 or ufb.cnt != 1:return -1return ans

总结

• 由删除变成增加
• 并查集模板修改，联通分量统计
• 边的优先级