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

Материал из DISCOPAL
Перейти к: навигация, поиск
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]:
                        groups[group[anc]].add(group[i])
                    else:
                        items[group[i]][anc].add(i)
            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
 
                visiting.add(node)
                visited.add(node)
                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