树中的拓扑排序

注意事项
（1）对于无向图，度为1的节点视为叶子结点，一般通过一个队列可以进行维护，清空一次队列内元素的过程相当于把最外围的叶子结点删除一波，对于队列内的结点，遍历其邻居，修改其度数减一，如果为1那么加入队列。
注意：
（a）不需要vis数组，因为我们只会把度数为1的节点加入队列，一个节点只有一次机会度数为1！
（b）特殊情况下，可能图中只有两个叶子节点相连，这时候需要特殊处理，可以参见第二道例题。
（c）每次我们往队列中加入一个节点，就代表删除一条边，一般情况下是对的，除非是（b）中的特殊情况，这条边会删除两次。

求树的中心节点

最小高度树
这道题还可以用换根DP来做，做法比较巧妙。
解法一 拓扑排序，找到中心节点组就是答案

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1)  return {0};
        vector<int>cnt(n,0);
        vector<int>v;
        vector<vector<int>>adj(n,v);
        for(auto obj : edges){
            int a = obj[0],b = obj[1];
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
            cnt[a]++;
            cnt[b]++;
        }
        queue<int>q;
        vector<int>ret;
        for(int i = 0;i<n;i++){
            if(cnt[i] == 1){
                q.push(i);
            }
        }
        int tot = q.size();
        while(tot<n){
            int k = q.size();
            while(k--){
                auto tmp = q.front();
                q.pop();
                for(auto next : adj[tmp]){
                    cnt[next]--;
                    if(cnt[next] == 1){
                        q.push(next);
                        tot++;
                    }
                }
            }
        }
        while(!q.empty()){
            ret.emplace_back(q.front());
            q.pop();
        }
        return ret;
    }
};
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

解法二 换根DP

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int ret = 0;
    int height = 100000;
    int depth[20005] = {0};
    int ans[20005] = {0};
    int dfs(int id,vector<vector<int>>&adj,int fa){
        int mx_height = 0;
        for(auto next : adj[id]) {
            if (next == fa) continue;
            int val = dfs(next,adj,id)+1;
            if(val > mx_height){
                mx_height = val;
            }
        }
        depth[id] = mx_height;
        return mx_height;
    }
    void search(int id,vector<vector<int>>&adj,int fa){
        int mx = 0,se = 0;
        //这里每次search开头计算mx,se是精髓，不能在外面预处理好，因为depth数组是在变化的
        for(auto next : adj[id]){
            int d = depth[next]+1;
            if(d > mx){
                se = mx;
                mx = depth[next]+1;
            //易错，不能省去这个else if！
            }else if(d > se){
                se = d;
            }
        }
        ans[id] = mx;
        height = min(height,mx);
        for(auto next : adj[id]){
            if(next == fa)   continue;
            if(mx == depth[next]+1){
                depth[id] = se;
            }else{
                depth[id] = mx;
            }
            search(next,adj,id);
        }
    }
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int>v;
        vector<vector<int>>adj(n,v);
        for(auto obj : edges){
            int a = obj[0],b = obj[1];
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
        }
        dfs(0,adj,-1);
        search(0,adj,-1);
        vector<int>ret;
        for(int i = 0;i<n;i++){
            if(ans[i] == height){
                ret.emplace_back(i);
            }
        }
        return ret;
    }
};

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

进阶版题目

收集树中的金币
注意这道题中对于ret边数的处理，对于队列中的叶子节点，统统减去一个边数，只有当图中仅两个结点相连，且都为叶子结点时，同一条边会被减去两次，剩余边数会变为负值，但是答案是0。所以将其与0取最大值。

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        vector<int>v;
        vector<vector<int>>adj(n,v);
        vector<int>cnt(n,0);
        for(auto obj : edges){
            int a = obj[0],b = obj[1];
            cnt[a]++;
            cnt[b]++;
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
        }
        int ret = n-1;
        queue<int>q;
        for(int i = 0;i<n;i++){
            if(cnt[i] == 1 && coins[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            ret--;
            auto tmp = q.front();
            q.pop();
            for(auto next : adj[tmp]){
                cnt[next]--;
                if(coins[next] == 0 && cnt[next] == 1){
                    q.push(next);
                }
            }
        }
        for(int i = 0;i<n;i++){
            if(cnt[i] == 1 && coins[i] == 1){
                q.push(i);
            }
        }
        for(int i = 0;i<2;i++){
            int k = q.size();
            while(k--){
                ret--;
                auto tmp = q.front();
                q.pop();
                for(auto next : adj[tmp]){
                    cnt[next]--;
                    if(cnt[next] == 1){
                        q.push(next);
                    }
                }
            }
        }
        return max(ret*2,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