310. Minimum Height Trees

bfs+topological sort O(n) time O(n) space
从外往里『剥洋葱』直到还剩1到2个节点为止，如果设置一个超级源点连接每个1度的点，则相当于单源最短路径

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n < 2) return {0};
        vector<unordered_set<int>> g(n);
        for (const auto &e : edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        list<int> q;
        for (int i = 0; i < n; ++i) {
            if (g[i].size() == 1) { // 叶节点『入度为0』
                q.push_back(i);
            }
        }
        while (n > 2) { // 还剩最多2个『入度为0』的节点时跳出循环，不能直接看队列大小，队列里放的只是当前『入度为0』的节点
            n -= size(q);
            for (int i = size(q); i > 0; --i) {
                int u = q.front(); q.pop_front();
                for (int v : g[u]) {
                    g[v].erase(u); // 从邻居那删除『我』
                    if (g[v].size() == 1) { // 为了避免重复入队列，只有还连着最后一条边的时候再入
                        q.push_back(v);
                    }
                }
            }
        }
        return vector<int>(begin(q), end(q));
    }
};

纯topological sort O(n²) time O(n) space

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n < 2) return {0};
        unordered_map<int, unordered_set<int>> g;
        for (const auto &e : edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        vector<int> res;
        while (!g.empty()) {
            res.clear();
            for (const auto &[i, _] : g) {
                if (g.count(i) && g[i].size() < 2) {
                    res.push_back(i);
                }
            }
            for (int u : res) {
                for (int v : g[u]) {
                    g[v].erase(u);
                }
                g.erase(u);
            }
        }
        return res;
    }
};