1
class Solution {
2
  // topological sort group first, then node within the group
3
  private List<Integer>[] groups;
4
  private List<Integer>[] graph;
5
  // indegrees of node
6
  private int[] indegrees;
7
  // indegrees of group
8
  private int[] indegreeGroups;
9

10
  public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
11
    buildGroups(n, group);
12
    buildGraph(n, beforeItems, group);
13
    int[] result = new int[n];
14
    int top = -1;
15
    Queue<Integer> queue = new LinkedList<>();
16
    for (int i = 0; i < n; i++) {
17
      if (indegreeGroups[i] == 0) {
18
        queue.offer(i);
19
      }
20
    }
21
    while (!queue.isEmpty()) {
22
      Integer groupId = queue.poll();
23
      List<Integer> groupItems = groups[groupId];
24
      if (groupItems == null) continue;
25
      Queue<Integer> itemQueue = new LinkedList<>();
26
      for (var item : groupItems) {
27
        if (indegrees[item] == 0) {
28
          itemQueue.offer(item);
29
        }
30
      }
31
      while (!itemQueue.isEmpty()) {
32
        Integer item = itemQueue.poll();
33
        result[++top] = item;
34
        if (graph[item] == null) continue;
35
        for (var neighbor : graph[item]) {
36
          indegrees[neighbor]--;
37
          if (group[neighbor] != groupId) {
38
            if (--indegreeGroups[group[neighbor]] == 0) {
39
              queue.offer(group[neighbor]);
40
            }
41
          } else if (indegrees[neighbor] == 0) {
42
            itemQueue.offer(neighbor);
43
          }
44
        }
45
      }
46
    }
47
    if (top < n - 1) return new int[] {};
48
    return result;
49
  }
50

51
  private void buildGroups(int n, int[] group) {
52
    // build groups;
53
    groups = new List[n];
54
    int index = n - 1;
55
    for (int i = 0; i < n; i++) {
56
      if (group[i] == -1) {
57
        // virtual group
58
        group[i] = index--;
59
      }
60
      if (groups[group[i]] == null) {
61
        groups[group[i]] = new ArrayList<>();
62
      }
63
      groups[group[i]].add(i);
64
    }
65
  }
66

67
  private void buildGraph(int n, List<List<Integer>> beforeItems, int[] group) {
68
    graph = new List[n];
69
    indegrees = new int[n];
70
    indegreeGroups = new int[n];
71
    for (int i = 0; i < n; i++) {
72
      for (int j : beforeItems.get(i)) {
73
        if (graph[j] == null) {
74
          graph[j] = new ArrayList<>();
75
        }
76
        graph[j].add(i);
77
        indegrees[i]++;
78
        if (group[i] != group[j]) {
79
          indegreeGroups[group[i]]++;
80
        }
81
      }
82
    }
83
  }
84
}