LeetCode 310: Деревья минимальной высоты

Aug 20 2020

Размещаю мой код для проблемы с LeetCode, если вы хотите просмотреть, сделайте это. Спасибо за уделенное время!

Проблема

Для неориентированного графа с древовидными характеристиками мы можем выбрать любой узел в качестве корня. Тогда результирующий граф представляет собой корневое дерево. Среди всех возможных корневых деревьев деревья с минимальной высотой называются деревьями минимальной высоты (MHT). Имея такой график, напишите функцию для поиска всех MHT и возврата списка их корневых меток.

Формат

Граф содержит n узлов, которые помечены от 0 до n - 1. Вам будет дано число n и список неориентированных ребер (каждое ребро представляет собой пару меток).

Вы можете предположить, что на ребрах не будет никаких повторяющихся кромок. Поскольку все ребра неориентированы, [0, 1] совпадает с [1, 0] и, следовательно, не будет появляться вместе на ребрах.

Пример 1:

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]

Пример 2:

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Заметка:

Согласно определению дерева в Википедии: «дерево - это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любой связный граф без простых циклов - это дерево ». Высота корневого дерева - это количество ребер на самом длинном нисходящем пути между корнем и листом.

Код

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_set>
#include <algorithm>

static const struct Solution {
        using ValueType = std::uint_fast16_t;

        static const std::vector<int> findMinHeightTrees(
            const int n,
            const std::vector<std::vector<int>>& edges
        ) {
            std::vector<int> buff_a;
            std::vector<int> buff_b;
            std::vector<int>* ptr_a = &buff_a;
            std::vector<int>* ptr_b = &buff_b;

            if (n == 1) {
                buff_a.emplace_back(0);
                return buff_a;
            }

            if (n == 2) {
                buff_a.emplace_back(0);
                buff_a.emplace_back(1);
                return buff_a;
            }

            std::vector<Node> graph(n);

            for (const auto& edge : edges) {
                graph[edge[0]].neighbors.insert(edge[1]);
                graph[edge[1]].neighbors.insert(edge[0]);
            }

            for (ValueType node = 0; node < n; ++node) {
                if (graph[node].isLeaf()) {
                    ptr_a->emplace_back(node);
                }
            }

            while (true) {
                for (const auto& leaf : *ptr_a) {
                    for (const auto& node : graph[leaf].neighbors) {
                        graph[node].neighbors.erase(leaf);

                        if (graph[node].isLeaf()) {
                            ptr_b->emplace_back(node);
                        }
                    }
                }

                if (ptr_b->empty()) {
                    return *ptr_a;
                }

                ptr_a->clear();
                std::swap(ptr_a, ptr_b);
            }
        }

    private:
        static const struct Node {
            std::unordered_set<ValueType> neighbors;
            const bool isLeaf() {
                return std::size(neighbors) == 1;
            }
        };
};


Рекомендации

  • Проблема

  • Обсудить

  • Вики

Ответы

2 vnp Aug 21 2020 at 00:20

А тройно вложенные петли всегда выглядят устрашающе. Особенно с while (true).

Прежде всего, поверьте себе. Листовой узел (а он ptr_aсодержит только листы) имеет только одного соседа. В

for (const auto& node : graph[leaf].neighbors)

цикл эффективно

auto& node = graph[leaf].neighbors.begin();

Во-вторых, пожалуйста, никаких голых петель. И еще функций, пожалуйста. В

for (const auto& leaf : *ptr_a)

чернослив листья с дерева. Разложите его на множители в prune_leavesфункцию, которая вернет набор (технически вектор) новых листьев:

leaves = prune_leaves(leaves, graph);

В-третьих, внешний цикл должен естественным образом завершиться, когда останется менее 3 листьев.

Наконец, отделите ввод-вывод от бизнес-логики. Тем не менее, код вроде

    graph = build_graph();
    leaves = collect_leaves(graph);
    while (leaves.size() < 3) {
        leaves = prune_leaves(leaves, graph);
    }
    return leaves;

получит мое одобрение. Обратите внимание на то, как ptr_aи ptr_b- не самые описательные имена - исчезают.