Leetcode 2603. Collect Coins in a Tree

[Woodyiiiiiii]

拓扑排序Topological Sort题型。

类似题目：

• 2603. Collect Coins in a Tree
• 1857. Largest Color Value in a Directed Graph
• 2050. Parallel Courses III
• 310. Minimum Height Trees
• 2192. All Ancestors of a Node in a Directed Acyclic Graph

参考资料：

• 拓扑排序 + 记录入队时间（Python/Java/C++/Go）

---

以下是No.2603的思考逻辑，如何一步步想到要用拓扑排序和改写的。

首先想到就是转换题目内容，题目要求其实也就是计算树中距离有金币的叶子结点为2的点之间有多少边，因为不是叶子结点的金币节点已经在路上顺手拿到了。

接着，因为树也有没金币的叶子结点，这些节点已经彻底没用了，我们需要排除掉，对树剪枝。用什么方法剪枝呢？第一想法是DFS，从这些没金币的叶子结点开始，然后改写度数。改善下，DFS容易超时，为了保证O(n)复杂度我们需要同步进行BFS。这样这个剪枝算法就是拓扑排序了。所以变成了用拓扑排序剪枝。

剪完枝后，我们下一步要计算树中距离叶子结点为2以上的节点个数/边个数。同理，我们也需要从多个叶子结点开始BFS，涉及到出度入度。这种多源BFS也可以用拓扑排序。用DP缓存的写法记录每个结点的层级。

最后遍历所有边，如果边的两个结点层级(距离叶子结点)超过或等于2，就将答案加2。

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        Map<Integer, Set<Integer>> edgeMap = new HashMap<>();
        int n = coins.length;
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int s = edge[0], t = edge[1];
            edgeMap.computeIfAbsent(s, k -> new HashSet<>()).add(t);
            edgeMap.computeIfAbsent(t, k -> new HashSet<>()).add(s);
            degree[s]++;
            degree[t]++;
        }

        // first topological sort
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!edgeMap.containsKey(node)) continue;
            for (int child : edgeMap.get(node)) {
                degree[child]--;
                if (degree[child] == 1 && coins[child] == 0) {
                    queue.offer(child);
                }
            }
        }

        // second topological sort
        int[] time = new int[n];
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 1) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!edgeMap.containsKey(node)) continue;
            for (int child : edgeMap.get(node)) {
                degree[child]--;
                if (degree[child] == 1) {
                    time[child] = time[node] + 1;
                    queue.offer(child);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            int s = edge[0], t = edge[1];
            if (time[s] >= 2 && time[t] >= 2) {
                res += 2;
            }
        }
        return res;
    }
}

拓扑排序总结：
一般题目类型：给定顺序/树/有向图/无项图
特点：从叶子结点出发，操作度数，可以剪枝，记录每个每个结点距离叶子结点的消耗/距离
本质：多源BFS

---

No.2050类似一个DP。

No.1857也是。在拓扑的基础上增加了DP的思想，每次比较最大颜色值，从而选择最长的那条路。DP的思想暗含了比较的思路