(topsort)310. 最小高度树

310. 最小高度树

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto e:edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b), g[b].push_back(a);
            d[a]++, d[b]++;
        }
        queue<int> q, tmp;
        for (int i = 0; i < n; i++) {
            if (d[i] <= 1)q.push(i);
        }

        while (q.size()) {
            tmp = q;
            queue<int> nxt;
            while (q.size()) {
                int u = q.front();
                d[u]--;
                q.pop();
                for (auto i:g[u]) {
                    if (--d[i] == 1)nxt.push(i);
                }
            }
            q = nxt;
        }
        vector<int> res;
        while (tmp.size()) {
            res.push_back(tmp.front());
            tmp.pop();
        }
        return res;
    }
};