无向树上的拓扑排序【力扣周赛 338——T4】

题目链接： https://leetcode.cn/problems/collect-coins-in-a-tree/description/

  注意无向图上拓扑排序是检测du[u] == 1，有向图中是din[u] == 0。

  本题还用到了一个拓扑排序的技巧：利用拓扑排序在图上删除一些不要的点。 这里是无向图，所以方式就是将这些点的度变为 $0$。那么在之后就不会用来加入队列了。

  该方法来自基环树的操作（下次详细说明）

具体讲解见文章：=====>《基环树与拓扑排序技巧》

  在这里，我们将没有金币的子树全部删除了（因为进入这些子树完全是浪费时间，一定不是最优解），就是通过从没有金币的叶子结点出发，跑一边拓扑排序。这样剩下的叶子结点都是有金币的，然后我们将这些叶子加入队列，再跑一次拓扑排序，并且计算到每个点的时间。只有时间大于等于 $2$ 的点组成的边才是我们需要通过的，且需要通过两次（这里是贪心思想，因为我们一次能回收距离当前节点距离为 $2$ 以内的所有金币，所以肯定是在最远处回收就行了）。

AC代码：

class Solution {
public:
    int h[30010], e[60010], ne[60010], idx;
    int du[30010], time[30010];
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }

    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        memset(h, -1, sizeof h);
        for(auto& t : edges){
            int a = t[0], b = t[1];
            add(a, b), add(b, a);
            du[a]++, du[b]++;
        }

        int q[30010], hh = 0, tt = -1;
        //用拓扑排序「剪枝」：去掉没有金币的子树
        for(int i = 0; i < n; i++){
            if(du[i] == 1 && coins[i] == 0) q[++tt] = i;
        }
        while(hh <= tt){
            auto t = q[hh++];
            for(int i = h[t]; ~i; i = ne[i]){
                int j = e[i];
                if(--du[j] == 1 && coins[j] == 0) q[++tt] = j;
            }
        }

        //统计时间
        hh = 0, tt = -1;
        for(int i = 0; i < n; i++){
            if(du[i] == 1 && coins[i] == 1) q[++tt] = i;  //有金币的叶子
        }
        while(hh <= tt){
            auto t = q[hh++];
            for(int i = h[t]; ~i; i = ne[i]){
                int j = e[i];
                if(--du[j] == 1){
                    time[j] = time[t] + 1;
                    q[++tt] = j;
                }
            }
        }

        int ans = 0;
        for(auto& t : edges){
            if(time[t[0]] >= 2 && time[t[1]] >= 2) ans += 2;
        }
        return ans;
    }
};