1579. 保证图可完全遍历

题目描述

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。

给你一个数组 edges ，其中 edges[i] = [type_i, u_i, v_i] 表示节点 u_i 和 v_i 之间存在类型为 type_i 的双向边。请你在保证图仍能够被 Alice 和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

示例 1：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

示例 2：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

示例 3：

输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

提示：

1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
所有元组 (type_i, u_i, v_i) 互不相同

解法一：并查集

 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78


type UnionFind struct {
    parent []int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{parent: make([]int, n)}
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Clone() *UnionFind {
    replica := &UnionFind{parent: make([]int, len(uf.parent))}
    copy(replica.parent, uf.parent)
    return replica
}

func (uf *UnionFind) Find(i int) int {
    if uf.parent[i] != i {
        uf.parent[i] = uf.Find(uf.parent[i])
    }
    return uf.parent[i]
}

func (uf *UnionFind) Merge(i, j int) bool {
    iF, jF := uf.Find(i), uf.Find(j)
    if iF != jF {
        uf.parent[iF] = jF
        return false
    }
    return true
}

func (uf *UnionFind) Count() int {
    ans := 0
    for i := 0; i < len(uf.parent); i++ {
        if uf.parent[i] == i {
            ans++
        }
    }
    return ans
}

func maxNumEdgesToRemove(n int, edges [][]int) int {
    BobUf := NewUnionFind(n + 1)
    ans := 0
    for _, edge := range edges {
        if edge[0] == 3 {
            u, v := edge[1], edge[2]
            if BobUf.Merge(u, v) {
                ans++
            }
        }
    }
    AliceUf := BobUf.Clone()
    for _, edge := range edges {
        u, v := edge[1], edge[2]
        if edge[0] == 1 {
            // Only for Alice
            if AliceUf.Merge(u, v) {
                ans++
            }
        } else if edge[0] == 2 {
            // Only for Bob
            if BobUf.Merge(u, v) {
                ans++
            }
        }
    }
    // 因为顶点的编号从 1 开始开始编号，故 uf.parent[0] == 0 会导致
    // 多计算一个连通分量，故整个图不连通的条件是 AliceUf.Count() > 2
    // 而不是 AliceUf.Count() > 1
    if AliceUf.Count() > 2 || BobUf.Count() > 2 {
        return -1
    }
    return ans
}