leetcode

0 class Solution {

1 public:

2 vector<int> sortItems(int n, int m, vector<int> &group, const vector<vector<int>> &beforeItems) {

3 for (int &g : group)

4 if (g == -1) g = m++;

5

6 vector<unordered_set<int>> gadj(m);

7 vector<vector<int>> adj(n), ordered(m);

8 vector<int> gcount(m, 0), count(n, 0);

9 queue<int> q;

10

11 for (int i = 0; i < n; i++) {

12 count[i] = beforeItems[i].size();

13 for (int elem : beforeItems[i]) {

14 adj[elem].push_back(i);

15 if (group[elem] == group[i]) continue;

16 if (gadj[group[elem]].count(group[i])) continue;

17 gadj[group[elem]].insert(group[i]);

18 gcount[group[i]]++;

19 }

20 }

21

22 int cnt = 0;

23 for (int i = 0; i < n; i++)

24 if (!count[i]) q.push(i);

25 while (!q.empty()) {

26 const int root = q.front();

27 ordered[group[root]].push_back(root);

28 for (int next : adj[q.front()]) {

29 if (!--count[next]) q.push(next);

30 }

31 q.pop();

32 cnt++;

33 }

34

35 if (cnt != n) return {};

36

37 vector<int> res;

38 for (int i = 0; i < m; i++)

39 if (!gcount[i]) q.push(i);

40 while (!q.empty()) {

41 const int root = q.front();

42 res.insert(res.end(), ordered[root].begin(), ordered[root].end());

43 for (int next : gadj[q.front()]) {

44 if (!--gcount[next]) q.push(next);

45 }

46 q.pop();

47 }

48

49 return res.size() == n ? res : vector<int>();

50 }

51 };