Задача: 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 {
    func sortItems(_ n: Int, _ m: Int, _ group: [Int], _ beforeItems: [[Int]]) -> [Int] {
        var group = group
        var groupId = m
        for i in 0..<n {
            if group[i] == -1 {
                group[i] = groupId
                groupId += 1
            }
        }

        var itemGraph = [Int: [Int]]()
        var itemIndegree = [Int](repeating: 0, count: n)
        for i in 0..<n { itemGraph[i] = [] }

        var groupGraph = [Int: [Int]]()
        var groupIndegree = [Int](repeating: 0, count: groupId)
        for i in 0..<groupId { groupGraph[i] = [] }

        for curr in 0..<n {
            for prev in beforeItems[curr] {
                itemGraph[prev]?.append(curr)
                itemIndegree[curr] += 1
                if group[curr] != group[prev] {
                    groupGraph[group[prev]]?.append(group[curr])
                    groupIndegree[group[curr]] += 1
                }
            }
        }

        let itemOrder = topologicalSort(itemGraph, itemIndegree)
        let groupOrder = topologicalSort(groupGraph, groupIndegree)
        if itemOrder.isEmpty || groupOrder.isEmpty { return [] }

        var orderedGroups = [Int: [Int]]()
        for item in itemOrder { orderedGroups[group[item], default: []].append(item) }

        var answerList = [Int]()
        for groupIndex in groupOrder { answerList.append(contentsOf: orderedGroups[groupIndex, default: []]) }

        return answerList
    }

    private func topologicalSort(_ graph: [Int: [Int]], _ indegree: [Int]) -> [Int] {
        var visited = [Int]()
        var stack = [Int]()
        for key in graph.keys { if indegree[key] == 0 { stack.append(key) } }

        while !stack.isEmpty {
            let curr = stack.removeLast()
            visited.append(curr)
            for next in graph[curr, default: []] { if --indegree[next] == 0 { stack.append(next) } }
        }

        return visited.count == graph.keys.count ? visited : []
    }
}

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