1from collections import defaultdict, deque
2
3def topologicalSort(n, adjList, indegree):
4    order = []
5    zeroIndegree = deque([i for i in range(n) if indegree[i] == 0])
6    while zeroIndegree:
7        node = zeroIndegree.popleft()
8        order.append(node)
9        for neighbor in adjList[node]:
10            indegree[neighbor] -= 1
11            if indegree[neighbor] == 0:
12                zeroIndegree.append(neighbor)
13    return order if len(order) == n else []
14
15
16def sortItems(n, m, group, beforeItems):
17    # Step 1: Assign temporary groups to items with a group of -1.
18    new_group = m  # Start numbering new groups from m
19    for i in range(n):
20        if group[i] == -1:
21            group[i] = new_group
22            new_group += 1
23
24    # Step 2: Item graph and indegree
25    item_graph = defaultdict(list)
26    item_indegree = [0] * n
27
28    # Step 3: Group graph and indegree
29    group_graph = defaultdict(list)
30    group_indegree = [0] * new_group
31
32    for i in range(n):
33        for before in beforeItems[i]:
34            item_graph[before].append(i)
35            item_indegree[i] += 1
36            if group[i] != group[before]:
37                if group[i] not in group_graph[group[before]]:
38                    group_graph[group[before]].append(group[i])
39                    group_indegree[group[i]] += 1
40
41    # Step 4: Topological sort groups and items
42    group_order = topologicalSort(new_group, group_graph, group_indegree)
43    if not group_order:
44        return []
45
46    item_order = topologicalSort(n, item_graph, item_indegree)
47    if not item_order:
48        return []
49
50    # Step 5: Map order back to the result by groups
51    items_by_group = defaultdict(list)
52    for item in item_order:
53        items_by_group[group[item]].append(item)
54
55    result = []
56    for grp in group_order:
57        result.extend(items_by_group[grp])
58
59    return result
60

1#include <vector>
2#include <queue>
3#include <unordered_map>
4#include <unordered_set>

using namespace std;

vector<int> topologicalSortUsingPQ(int n, vector<vector<int>>& graph, vector<int>& indegree) {
    priority_queue<int, vector<int>, greater<int>> zeroIndegree;
    vector<int> order;
    for (int i = 0; i < n; ++i) {
        if (indegree[i] == 0) {
            zeroIndegree.push(i);
        }
    }
    
    while (!zeroIndegree.empty()) {
        int node = zeroIndegree.top();
        zeroIndegree.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (--indegree[neighbor] == 0) {
                zeroIndegree.push(neighbor);
            }
        }
    }
    return order.size() == n ? order : vector<int>();
}

vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
    int newGroupId = m;
    for (int i = 0; i < n; ++i) {
        if (group[i] == -1) {
            group[i] = newGroupId++;
        }
    }

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

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

    vector<int> groupOrder = topologicalSortUsingPQ(newGroupId, groupGraph, groupIndegree);
    if (groupOrder.empty()) return {};

    vector<int> itemOrder = topologicalSortUsingPQ(n, itemGraph, itemIndegree);
    if (itemOrder.empty()) return {};

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

    vector<int> result;
    for (int grp : groupOrder) {
        result.insert(result.end(), itemsGrouped[grp].begin(), itemsGrouped[grp].end());
    }

    return result;
}