leetcode：1579. 保证图可完全遍历【并查集思路】

题目截图

题目分析

• 从删除比较难，考虑增加
• 增加的过程中无用的边就可以删除
• 考虑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 = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def 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:
        # edges预处理为[0, n - 1]
        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
        
        #print(ufa.parent)
        #print(ufb.parent)
        if ufa.cnt != 1 or ufb.cnt != 1:
            return -1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

总结

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