LeetCode/cpp/minimum-height-trees.cpp

#include <algorithm>
#include <queue>
#include <vector>

struct Solution {
    using graph_t = std::vector<std::vector<int>>;

  public:
    std::vector<int>
    findMinHeightTrees(int n, const std::vector<std::vector<int>> &edges) {
        auto g = graph(n, edges);

        std::vector<bool> visited(n);
        auto nodes = leafs(g, visited);
        auto d = degrees(g);

        std::vector<int> min_height_roots;
        while (!nodes.empty()) {
            auto size = nodes.size();
            min_height_roots.clear();

            for (auto i = 0u; i < size; ++i) {
                auto u = nodes.front();
                nodes.pop();

                min_height_roots.push_back(u);
                for (auto v : g[u]) {
                    if (visited[v]) {
                        continue;
                    }

                    if ((--d[v]) == 1) {
                        visited[v] = true;
                        nodes.push(v);
                    }
                }
            }
        }

        return min_height_roots;
    }

  private:
    graph_t graph(int n, const graph_t &edges) {
        graph_t neighbors(n);

        for (const auto &e : edges) {
            auto [u, v] = std::make_pair(e[0], e[1]);
            neighbors[u].push_back(v);
            neighbors[v].push_back(u);
        }

        return neighbors;
    }

    std::queue<int> leafs(const graph_t &g, std::vector<bool> &visited) {
        std::queue<int> nodes;

        for (auto u = 0u; u < g.size(); ++u) {
            if (g[u].size() >= 2) {
                continue;
            }

            visited[u] = true;
            nodes.push(u);
        }

        return nodes;
    }

    std::vector<int> degrees(const graph_t &g) {
        std::vector<int> d(g.size());

        for (auto i = 0u; i < g.size(); ++i) {
            d[i] = g[i].size();
        }

        return d;
    }
};