Sort Items by Groups Respecting Dependencies

Problem Id: 1203 Difficulty: Hard Tag: Depth-first Search Tag: Graph Tag: Topological Sort


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):
        self.adj[p].add(q)

    def reverse(self):
        rev = DiGraph(self.size)
        for p in range(self.size):
            for q in self.adj[p]:
                rev.add_edge(q, 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]:
                    group_graph.add_edge(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]:
                    graph.add_edge(vertex, 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