Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

👨‍💻 Алгоритм:

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; ++i) if (group[i] == -1) group[i] = groupId++;

        vector<vector<int>> itemGraph(n), groupGraph(groupId);
        vector<int> itemIndegree(n, 0), groupIndegree(groupId, 0);

        for (int curr = 0; curr < n; ++curr) {
            for (int prev : beforeItems[curr]) {
                itemGraph[prev].push_back(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]].push_back(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }

        vector<int> itemOrder = topologicalSort(itemGraph, itemIndegree);
        vector<int> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (itemOrder.empty() || groupOrder.empty()) return {};

        unordered_map<int, vector<int>> orderedGroups;
        for (int item : itemOrder) orderedGroups[group[item]].push_back(item);

        vector<int> answerList;
        for (int groupIndex : groupOrder) answerList.insert(answerList.end(), orderedGroups[groupIndex].begin(), orderedGroups[groupIndex].end());

        return answerList;
    }

private:
    vector<int> topologicalSort(const vector<vector<int>>& graph, vector<int>& indegree) {
        vector<int> visited;
        stack<int> stack;
        for (int i = 0; i < graph.size(); ++i) if (indegree[i] == 0) stack.push(i);

        while (!stack.empty()) {
            int curr = stack.top();
            stack.pop();
            visited.push_back(curr);
            for (int next : graph[curr]) if (--indegree[next] == 0) stack.push(next);
        }

        return visited.size() == graph.size() ? visited : vector<int>();
    }
};

Ставь 👍 и забирай 📚 Базу знаний