Задача: 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 {
    function sortItems($n, $m, $group, $beforeItems) {
        $groupId = $m;
        for ($i = 0; $i < $n; $i++) if ($group[$i] == -1) $group[$i] = $groupId++;

        $itemGraph = array_fill(0, $n, []);
        $groupGraph = array_fill(0, $groupId, []);
        $itemIndegree = array_fill(0, $n, 0);
        $groupIndegree = array_fill(0, $groupId, 0);

        for ($curr = 0; $curr < $n; $curr++) {
            foreach ($beforeItems[$curr] as $prev) {
                $itemGraph[$prev][] = $curr;
                $itemIndegree[$curr]++;
                if ($group[$curr] != $group[$prev]) {
                    $groupGraph[$group[$prev]][] = $group[$curr];
                    $groupIndegree[$group[$curr]]++;
                }
            }
        }

        $itemOrder = $this->topologicalSort($itemGraph, $itemIndegree);
        $groupOrder = $this->topologicalSort($groupGraph, $groupIndegree);
        if (empty($itemOrder) || empty($groupOrder)) return [];

        $orderedGroups = [];
        foreach ($itemOrder as $item) {
            $orderedGroups[$group[$item]][] = $item;
        }

        $answerList = [];
        foreach ($groupOrder as $groupIndex) {
            if (isset($orderedGroups[$groupIndex])) $answerList = array_merge($answerList, $orderedGroups[$groupIndex]);
        }

        return $answerList;
    }

    function topologicalSort($graph, $indegree) {
        $visited = [];
        $stack = [];
        foreach ($graph as $key => $value) if ($indegree[$key] == 0) $stack[] = $key;

        while (!empty($stack)) {
            $curr = array_pop($stack);
            $visited[] = $curr;
            foreach ($graph[$curr] as $next) {
                $indegree[$next]--;
                if ($indegree[$next] == 0) $stack[] = $next;
            }
        }

        return count($visited) == count($graph) ? $visited : [];
    }
}

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