2603. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

很有意思的一道题目。很难想到拓扑排序。拓扑排序经典要素，拓扑关系，度，队列。自底向上逐渐逼近。

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        /**
        因为求的是最少的边数
        主要思想是先逐步删去无用的边。
        第一步是收集没有金币的叶子，然后将其与父节点的边删掉
        第二步是收集有金币的叶子，然后删掉与父节点的边及其父节点与叶节点的边
         */
        int n = coins.length;

        // 存放全局拓扑关系
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e->new ArrayList());
        // 入度
        int[] degrees = new int[n];
        var q = new ArrayDeque<Integer>();
        int leftEdges = n-1;
        for(int[] edge:edges) {
            int x = edge[0], y = edge[1];
            g[x].add(y);
            g[y].add(x);
            degrees[x] ++;
            degrees[y] ++;
        }
        // 第一步是收集没有金币的叶子，然后将其与父节点的边删掉
        for(int i=0; i<n; i++) {
            if(degrees[i] == 1 && coins[i] == 0) {
                q.offer(i);
            }
        }
        while(!q.isEmpty()) {
            leftEdges --;
            for(int node:g[q.pop()]) {
                degrees[node] --;
                if(degrees[node] == 1 && coins[node] == 0) {
                    q.offer(node);
                }
            }

        }

        // 第二步是收集有金币的叶子，然后删掉与父节点的边及其父节点与叶节点的边
        for(int i=0; i<n; i++) {
            if(degrees[i] == 1 && coins[i] == 1) {
                q.offer(i);
            }
        }
        leftEdges -= q.size(); 
        
        while(!q.isEmpty()) {
            for(int node:g[q.pop()]) {
                degrees[node] --;
                if(degrees[node] == 1) {
                    leftEdges --;
                }
            }
        }
        return Math.max(2*leftEdges, 0);
    }
}
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