Ежедневная часть (e) C++ # 84, Общая проблема интервью C++: максимальное количество приглашений

Сегодня мы рассмотрим распространенную проблему собеседования: максимальное количество приглашений.

Учитывая массив целых чисел, где каждое целое число представляет предпочтение места (например, «pref[i] == j» означает, что человек «i» хочет сесть рядом с человеком «j»), определите максимальное количество людей, которых вы можете пригласить. сидеть за круглым столом, удовлетворяя предпочтения всех приглашенных.

Например, для ввода {1,2,0,4,3,3,4} лучшее, что мы можем сделать, это четыре человека, а именно 3,4,5 и 6, потому что 3 и 4 хотят сесть рядом с каждым. другой, позволяя 5 и 6 сидеть рядом с 3 и 4 соответственно.

Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/qjj69c1MM.

Решение

Этот тип проблемы требует некоторого начального анализа. Когда мы можем сажать людей за стол без конфликтов?

Наиболее очевидная ситуация — цикл: A→B→C→…→X→A

Поскольку мы можем посадить за стол только один велосипед, количество людей — это просто длина цикла.

Однако есть второй вариант. Рассмотрим пару людей, которые хотят сесть рядом друг с другом. Они образуют цикл размера два, но также позволяют другим людям сидеть рядом с ними: A → B → X ← → Y ← C ← D

Каждая группа является автономной, что позволяет нам рассадить столько людей, сколько мы хотим за столом.

Чтобы определить максимальное количество людей, которых мы можем пригласить, нам нужны две вещи. Мы должны обнаруживать циклы и вычислять самые длинные пути, заканчивающиеся циклами.

К счастью, топологическая сортировка — это линейный алгоритм времени выполнения, который может предоставить эту информацию.

#include <vector>
#include <queue>

int maximum_invitations(const std::vector<int>& preferences) {
    std::vector<int> edges(preferences.size(), 0);
    std::vector<int> paths(preferences.size(), 0);

    // Count the number of people that want to sit next to 
    // the i-th person.
    for (int i = 0; i < std::ssize(preferences); ++i)
        ++edges[preferences[i]];

    std::deque<int> q;
    // Initialize the queue with people that no one wants
    // to sit next to.
    for (int i = 0; i < std::ssize(edges); ++i)
        if (edges[i] == 0) q.push_back(i);

    // Topological sort
    while (!q.empty()) {
        int idx = q.front();
        q.pop_front();

        int target = preferences[idx];
        // Longest path
        paths[target] = std::max(paths[target], paths[idx] + 1);
        --edges[target];
        
        if (edges[target] == 0) q.push_back(target);
    }

    // At this point, the only non-zero elements are part of cycles.
    // The following code finds the largest cycle and for cycles of
    // size two, sums up the total path length.
    int max_cycle = 0;
    int two_sum = 0;
    for (int i = 0; i < std::ssize(edges); ++i) {
        if (edges[i] == 0) continue;

        int len = 0;
        int sum = 0;

        // Walk the cycle:
        int idx = i;
        while (edges[idx] != 0) {
            --edges[idx];
            sum += paths[idx] + 1;
            ++len;

            idx = preferences[idx];
        }

        max_cycle = std::max(max_cycle, len);
        if (len == 2) two_sum += sum;
    }

    // The maximum is either the longest cycle or the sum of 
    // the paths that have a two-cycle in the middle.
    return std::max(max_cycle, two_sum);
}

Откройте решение в Compiler Explorer.