题目截图
题目分析
从删除比较难,考虑增加 增加的过程中无用的边就可以删除 考虑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 -= 1 return True class Solution : def maxNumEdgesToRemove ( self, n: int , edges: List[ List[ int ] ] ) - > int : for i in range ( len ( edges) ) : edges[ i] [ 1 ] -= 1 edges[ 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 += 1 else : pass for t, u, v in edges: if t == 1 : if not ufa. merge( u, v) : ans += 1 elif t == 2 : if not ufb. merge( u, v) : ans += 1 if ufa. cnt != 1 or ufb. cnt != 1 : return - 1 return ans
总结
由删除变成增加 并查集模板修改,联通分量统计 边的优先级