# Участник:Danillich/SortItemsbyGroupsRespectingDependencies

Перейти к: навигация, поиск
```class Solution:
def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
# two graph topological sort
def makeGraphs():
items = collections.defaultdict(dict)
groups = {}
for i, g in enumerate(group):
items[g][i] = set()
if g not in groups:
groups[g] = set()

for i, ancestors in enumerate(beforeItems):
for anc in ancestors:
if group[i] != group[anc]:
else:
return items, groups

def sortGraph(G, stack):
visiting = set()
visited = set()
def dfs(node):
if node in visiting: return False
if node in visited: return True

for child in G[node]:
if not dfs(child):
return False
stack.append(node)
visiting.remove(node)
return True

for node in G:
if not dfs(node):
return []
return stack

items, groups = makeGraphs()
groupsStack = []
sortGraph(groups, groupsStack)
if not groupsStack:
return []

res = []
for g in reversed(groupsStack):
groupItems = []
sortGraph(items[g], groupItems)
if not groupItems:
return []
res.extend(reversed(groupItems))
return res```