【Leetcode】1579.保证图可完全遍历

1579.保证图可完全遍历

题目

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

  • 类型 1：只能由 Alice 遍历。
  • 类型 2：只能由 Bob 遍历。
  • 类型 3：Alice 和 Bob 都可以遍历（共享边）。

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

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -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 。

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

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

方法（并查集 + 贪心）

判断能否遍历整个图：
因为要保证Alice和Bob两个人都可以遍历整个图，所以要分别为Alice和Bob构造单独的并查集。

初始时，两人的并查集中集合数目都为节点数n。如果最后Alice的并查集中集合数目变为1，说明所有的顶点在Alice的并查集中都被连接到了一起，即Alice可以遍历整个图。Bob同理。

贪心策略：能使用共享边时就使用共享边，因为共享边让Alice和Bob在遍历时都可以使用。只用一条共享边就可以达到两条独享边的效果。因此我们先使用共享边对节点进行连接，之后再使用Alice和Bob的独享边进行连接。

注意：共享边同时可以连接Alice和Bob的并查集中的节点。而Alice的独享边只能连接Alice并查集中的节点。Bob的独享边只能连接Bob并查集中的节点。

判断一条边可否删除：
遍历到一条边时，只需要判断这条边的两个顶点此时在相应的并查集中是否已经在同一个集合内，如果是的话，那么就不再需要它进行连接，这条边可以删除。

代码

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
79
80
81
82
83
84
85
86
87
88
89
class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFindSet alice = new UnionFindSet();
        UnionFindSet bob = new UnionFindSet();
        List<Integer> nodes = new LinkedList<>();
        for(int i = 1; i <= n; i++)
            nodes.add(i);
        alice.makeSet(nodes);
        bob.makeSet(nodes);
        int res = 0;  //res代表可删除的边个数
        //先遍历所有的双向边
        for(int[] edge : edges){
            if(edge[0] == 3){
                boolean a = alice.union(edge[1], edge[2]);
                boolean b = bob.union(edge[1], edge[2]);
                //如果对于alice和bob，此边的两个顶点都已经在一个集合中，那么这条共享边可以删除
                if(!a && !b)
                    res++;
            }
        }
        //再遍历单向边
        for(int[] edge : edges){
            //如果这条边是alice独享的，那么判断它的两个顶点在alice的并查集中是否已在一个集合中，若是，则可删除
            if(edge[0] == 1){
                boolean canUnion = alice.union(edge[1], edge[2]);
                res += canUnion ? 0 : 1;
            }
            //bob同理
            else if(edge[0] == 2){
                boolean canUnion = bob.union(edge[1], edge[2]);
                res += canUnion ? 0 : 1;
            }
        }
        //如果两人中至少有一人不能遍历整个图，那么返回-1
        return alice.getSize() == 1 && bob.getSize() == 1 ? res : -1;
    }


}

class UnionFindSet{
    Map<Integer, Integer> fatherMap;
    Map<Integer, Integer> sizeMap;
    int size;  //size代表并查集中集合的数量
    public UnionFindSet(){
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
        size = 0;
    }
    public void makeSet(List<Integer> nodes){
        for(int node : nodes){
            sizeMap.put(node, 1);
            fatherMap.put(node, node);
        }
        size = nodes.size();
    }
    public int findHead(int node){
        int father = fatherMap.get(node);
        if(father != node){
            father = findHead(father);
        }
        fatherMap.put(node, father);
        return father;
    }
    //若成功进行union操作则返回true。
    //若a和b已经在一个集合中，不需要进行union操作则返回false
    public boolean union(int a, int b){
        int headA = findHead(a);
        int headB = findHead(b);
        if(headA != headB){
            int sizeA = sizeMap.get(headA);
            int sizeB = sizeMap.get(headB);
            if(sizeA < sizeB){
                fatherMap.put(headA, headB);
                sizeMap.put(sizeB, sizeA + sizeB);
            }
            else{
                fatherMap.put(headB, headA);
                sizeMap.put(sizeA, sizeA + sizeB);
            }
            size--;
            return true;
        }
        return false;
    }
    public int getSize(){
        return this.size;
    }
}