Leetcode 1203: Sort Items by Groups Respecting Dependencies

https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/description/

Notes:

This question is a hard question, due to its complicated logic. It is mainly about the topological sort algorithm.

First of all, there are more than one groups. And we need to run a topological sort to all the groups, to make sure they can be arranged;

Second, inside each group, we also need to run a topological sort, to make sure that they also can be arranged in the required orders.

The topological sort is a typical algorithm, which usually requires the indgrees of each note. Firstly we will start the sort with the node having a indgree of 0 which means there is no prerequisite. During visiting or sorting, we can gradually decrease the indgree of the unvisited node when their pre-nodes are visited. Once its indegree becomes 0, it can ready to be visited.

Please check the code below:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<int> res;
        unordered_map<int, set<int>> gs;//group structures;
        unordered_map<int, set<int>> group_graph;//group relations
        unordered_map<int, int> group_indgree;//group indgrees;
        unordered_map<int, set<int>> memb_graph;//member relations;
        unordered_map<int, int> memb_indgree;//memeber indgree;
       
        int num_group = m;
        for(int i=0; i<group.size(); ++i) {
            if(group[i] == -1) {//listed as one unique group
                group[i] = num_group++;
            }
            gs[group[i]].insert(i);
        }
       
        for(int to=0; to<beforeItems.size(); ++to) {
            int to_group = group[to];
            for(auto &from : beforeItems[to]) {
                int from_group = group[from];
                if(from_group == to_group) {//belong to the same sub-group;
                    if(!memb_graph[from].count(to)) {
                     memb_graph[from].insert(to);
                     ++memb_indgree[to];
      }
                }
                else {
      if(!group_graph[from_group].count(to_group)) {
                     group_graph[from_group].insert(to_group);
                     ++group_indgree[to_group];
      }
                }
            }
        }

        vector<int> group_res;
        queue<int> q;
        for(int i=0; i<num_group; ++i) {
            if(group_indgree[i] == 0) {
                q.push(i);
                group_res.push_back(i);
            }
        }
        while(q.size()) {
            int t = q.front();
            q.pop();
            for(auto &a : group_graph[t]) {
                if(group_indgree[a] == 0) continue;
                --group_indgree[a];
                if(group_indgree[a] == 0) {
                    q.push(a);
                    group_res.push_back(a);
                }
            }
        }
        if(group_res.size() != num_group) return {};
      
        for(auto &a : group_res) {//check each group
            int ct = 0;
            for(auto &b : gs[a]) {
                if(memb_indgree[b] == 0) {
                    q.push(b);
                    res.push_back(b);
                    ++ct;
                }
            }
            while(q.size()) {
                auto t = q.front();
                q.pop();
                for(auto &c : memb_graph[t]) {
                    if(memb_indgree[c] == 0) continue;
                    --memb_indgree[c];
                    if(memb_indgree[c] == 0) {
                        q.push(c);
                        res.push_back(c);
                        ++ct;
                    }
                }
            }
            if(ct != gs[a].size()) return {};
        }

        return res;
    }
};