Задача: 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⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

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

        var itemGraph = new Dictionary<int, List<int>>();
        var groupGraph = new Dictionary<int, List<int>>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph[i] = new List<int>();
        for (int i = 0; i < groupId; i++) groupGraph[i] = new List<int>();

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

        var itemOrder = TopologicalSort(itemGraph, itemIndegree);
        var groupOrder = TopologicalSort(groupGraph, groupIndegree);
        if (itemOrder.Count == 0 || groupOrder.Count == 0) return new int[0];

        var orderedGroups = new Dictionary<int, List<int>>();
        foreach (var item in itemOrder) {
            if (!orderedGroups.ContainsKey(group[item])) orderedGroups[group[item]] = new List<int>();
            orderedGroups[group[item]].Add(item);
        }

        var answerList = new List<int>();
        foreach (var groupIndex in groupOrder) {
            if (orderedGroups.ContainsKey(groupIndex)) answerList.AddRange(orderedGroups[groupIndex]);
        }

        return answerList.ToArray();
    }

    private List<int> TopologicalSort(Dictionary<int, List<int>> graph, int[] indegree) {
        var visited = new List<int>();
        var stack = new Stack<int>();
        foreach (var key in graph.Keys) if (indegree[key] == 0) stack.Push(key);

        while (stack.Count > 0) {
            var curr = stack.Pop();
            visited.Add(curr);
            foreach (var next in graph[curr]) if (--indegree[next] == 0) stack.Push(next);
        }

        return visited.Count == graph.Keys.Count ? visited : new List<int>();
    }
}

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