# Sort Items by Groups Respecting Dependencies     ## Intuition

For verteces with dependencies, we could use topological sort to get the order so that each vertex appear after all its dependencies. We can get the topological order, by calculating reverse postorder of a graph.

In this problem, we could first get the topological order of groups. Then, get topological order of verteces in each group.

Be notice that, the input is valid when there is cycle in the dependencies of groups or verteces.

## Solution

``````
class DiGraph:
def __init__(self, size):
self.size = size
self.adj = [set() for _ in range(size)]

def add_edge(self, p, q):

def reverse(self):
rev = DiGraph(self.size)
for p in range(self.size):
for q in self.adj[p]:
return rev

class PostOrder:
def __init__(self, digraph, origin=None):
self.cycle = False
self.on_stack = [False] * digraph.size
self.visited = [False] * digraph.size
self.postorder = []
if origin is None:
origin = range(digraph.size)
for i in origin:
if not self.visited[i]:
self.dfs(digraph, i)

def dfs(self, digraph, vertex):
self.visited[vertex] = True
self.on_stack[vertex] = True
for child in digraph.adj[vertex]:
if not self.visited[child]:
self.dfs(digraph, child)
elif self.on_stack[child]:
self.cycle = True
self.postorder.append(vertex)
self.on_stack[vertex] = False

class Solution:
def sortItems(self, n, m, group, beforeItems):
m = max(group) + 1
for i in range(n):
if group[i] == -1:
group[i] = m
m += 1

# Get the order of groups
group_graph = DiGraph(m)
for vertex in range(n):
for dep in beforeItems[vertex]:
if group[vertex] != group[dep]:
order = PostOrder(group_graph)
if order.cycle:
return []
group_order = order.postorder

# Get the order for verteces in each group
graph = DiGraph(n)
for vertex in range(n):
for dep in beforeItems[vertex]:
if group[vertex] == group[dep]:
order = PostOrder(graph)
if order.cycle:
return []

orderby_groups = [[] for _ in range(m)]
for i in order.postorder:
orderby_groups[group[i]].append(i)

ans = []
for g in group_order:
for i in orderby_groups[g]:
ans.append(i)
return ans
``````