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

1using System;
2using System.Collections.Generic;
3
4public class Solution {
    public IList<int> SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
        int newGroupId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
        }

        List<int>[] itemGraph = new List<int>[n], groupGraph = new List<int>[newGroupId];
        int[] itemIndegree = new int[n], groupIndegree = new int[newGroupId];

        for (int i = 0; i < n; i++) {
            itemGraph[i] = new List<int>();
        }

        for (int i = 0; i < newGroupId; i++) {
            groupGraph[i] = new List<int>();
        }

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

        var groupOrder = pqTopologicalSort(newGroupId, groupGraph, groupIndegree);
        if (groupOrder.Count == 0) return new List<int>();

        var itemOrder = pqTopologicalSort(n, itemGraph, itemIndegree);
        if (itemOrder.Count == 0) return new List<int>();

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

        var result = new List<int>();
        foreach (var grp in groupOrder) {
            if (itemsGrouped.ContainsKey(grp)) {
                result.AddRange(itemsGrouped[grp]);
            }
        }

        return result;
    }

    private List<int> pqTopologicalSort(int n, List<int>[] graph, int[] indegree) {
        var zeroIndegree = new SortedSet<int>();
        var order = new List<int>();

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                zeroIndegree.Add(i);
            }
        }

        while (zeroIndegree.Count > 0) {
            int node = zeroIndegree.Min;
            zeroIndegree.Remove(node);
            order.Add(node);
            foreach (var neighbor in graph[node]) {
                if (--indegree[neighbor] == 0) {
                    zeroIndegree.Add(neighbor);
                }
            }
        }

        return order.Count == n ? order : new List<int>();
    }
}