1
/*
2
    https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
3

4
    TC: O(n + m + E), E = No. of edges as seen from 'beforeItems' array
5
    SC: O(n + m)
6

7
    Looking at the problem, it is clearly a topological sort problem. But there
8
   are two things that needs ordering. The nodes within a group can have an
9
   ordering, as well the groups.
10

11
    Idea:
12
    1. Topological sort for nodes alone.
13
    2. Topological sort for just the groups
14
    3. In order to do above, we create two graphs. One graph just for the groups
15
   with m nodes, where the nodes are actually the group IDs. Another graph with
16
   size n, it is for the graph nodes.
17
    4. Then perform topological sort for both the graphs.
18
    5. Once we have the ordered nodes after topological sort, we fill the nodes
19
   of each group with that order.
20
    6. Then using the topological order of groups, just fill the nodes for each
21
   group.
22
*/
23
class Solution {
24
 public:
25
  // Topological Sort
26
  vector<int> topologicalSort(vector<unordered_set<int>> &graph, vector<int> &indegree) {
27
    vector<int> order;
28
    int processed = 0, n = graph.size();
29

30
    queue<int> q;
31
    // Add 0 indegree nodes
32
    for (int node = 0; node < n; node++)
33
      if (indegree[node] == 0) q.emplace(node);
34

35
    while (!q.empty()) {
36
      auto node = q.front();
37
      q.pop();
38

39
      // process the node
40
      ++processed;
41
      order.emplace_back(node);
42

43
      // Remove its dependence
44
      for (auto neighbor : graph[node]) {
45
        --indegree[neighbor];
46
        if (indegree[neighbor] == 0) q.emplace(neighbor);
47
      }
48
    }
49

50
    return processed < n ? vector<int>{} : order;
51
  }
52

53
  vector<int> sortItems(int n, int m, vector<int> &group, vector<vector<int>> &beforeItems) {
54
    // Each node without a group will be self contained in a new group with only
55
    // itself Set the new group id for each isolated node
56
    for (int node = 0; node < n; node++)
57
      if (group[node] == -1) group[node] = m++;
58

59
    // We create two graphs, one for the groups and another for the actual nodes
60
    vector<unordered_set<int>> group_graph(m), node_graph(n);
61
    // Stores the indegree for: Amongst Groups and nodes respectively
62
    vector<int> group_indegree(m, 0), node_indegree(n, 0);
63

64
    // Create cyclic graph for group and individual nodes
65
    for (auto node = 0; node < n; node++) {
66
      // Group to which the current node belongs
67
      int dst_group = group[node];
68
      // Source Groups on which the current node has a dependency
69
      for (auto src_node : beforeItems[node]) {
70
        int src_group = group[src_node];
71
        // check if the dependency is inter group or intra group
72
        // It is inter group dependency, make sure that the same dst_group was
73
        // not seen before, otherwise indegree will get additional 1, same logic
74
        // for the node_graph
75
        if (dst_group != src_group && !group_graph[src_group].count(dst_group)) {
76
          group_graph[src_group].emplace(dst_group);
77
          ++group_indegree[dst_group];
78
        }
79

80
        // Add the dependency amongst the nodes
81
        if (!node_graph[src_node].count(node)) {
82
          node_graph[src_node].emplace(node);
83
          ++node_indegree[node];
84
        }
85
      }
86
    }
87

88
    // Perform topological sort at a node level
89
    vector<int> ordered_nodes = topologicalSort(node_graph, node_indegree);
90
    // Perform topological sort at a group level
91
    vector<int> ordered_groups = topologicalSort(group_graph, group_indegree);
92
    // Overall order of nodes
93
    vector<int> order;
94

95
    // For each group, put the ordered nodes after topological sort
96
    vector<vector<int>> group_ordered_nodes(m);
97
    for (auto node : ordered_nodes) group_ordered_nodes[group[node]].emplace_back(node);
98

99
    // Now that within each group, all the nodes are ordered.
100
    // Using the topological sort info about the groups, just put the nodes in
101
    // that order
102
    for (auto group : ordered_groups)
103
      for (auto node : group_ordered_nodes[group]) order.emplace_back(node);
104

105
    return order;
106
  }
107
};