|
| 1 | +fromcollectionsimportdefaultdict,deque |
| 2 | +fromtypingimportList |
| 3 | +classSolution: |
| 4 | +# This function performs topological sort on a directed graph represented by successors and predecessors_count arrays. |
| 5 | +deftopologicalSort(self,successors:List[List[int]],predecessors_count:List[int],num_nodes:int)->List[int]: |
| 6 | +order= []# To store the topologically sorted nodes |
| 7 | +# Initialize a deque with all nodes that have no predecessors (i.e., in-degree of 0) |
| 8 | +nodes_with_no_predecessors=deque(nodefornodeinrange(num_nodes)ifnotpredecessors_count[node]) |
| 9 | + |
| 10 | +whilenodes_with_no_predecessors:# Process nodes while there are nodes without predecessors |
| 11 | +node=nodes_with_no_predecessors.popleft()# Get the node with no predecessors |
| 12 | +order.append(node)# Add the node to the sorted order |
| 13 | +forsuccessorinsuccessors[node]:# For each successor of the current node |
| 14 | +predecessors_count[successor]-=1# Decrement the in-degree of the successor |
| 15 | +ifnotpredecessors_count[successor]:# If the successor now has no predecessors |
| 16 | +nodes_with_no_predecessors.append(successor)# Add it to the queue for processing |
| 17 | + |
| 18 | +# If the number of nodes in the order is less than the total number of nodes, a cycle was detected |
| 19 | +returnorderiflen(order)==num_nodeselse []# Return the order if all nodes were sorted, else return empty list |
| 20 | + |
| 21 | +defsortItems(self,n:int,m:int,group:List[int],beforeItems:List[List[int]])->List[int]: |
| 22 | +# Step 1: Assign unique group IDs to items that don't belong to any group |
| 23 | +foriteminrange(n): |
| 24 | +ifgroup[item]==-1:# If the item doesn't belong to any group |
| 25 | +group[item]=m# Assign a new group ID |
| 26 | +m+=1# Increment the group ID for the next item |
| 27 | + |
| 28 | +# Step 2: Initialize graphs for item dependencies and group dependencies |
| 29 | +successors_group,successors_item= [[]for_inrange(m)], [[]for_inrange(n)]# Graphs for group and item dependencies |
| 30 | +predecessors_count_group,predecessors_count_item= [0]*m, [0]*n# Count of incoming edges (predecessors) for each group and item |
| 31 | + |
| 32 | +# Step 3: Build the dependency graphs based on beforeItems |
| 33 | +foriteminrange(n): |
| 34 | +current_group=group[item]# Get the group of the current item |
| 35 | +forbeforeinbeforeItems[item]:# Process each item that should come before the current item |
| 36 | +before_group=group[before]# Get the group of the item that should come before |
| 37 | + |
| 38 | +ifcurrent_group==before_group:# If the two items belong to the same group |
| 39 | +successors_item[before].append(item)# Add a dependency from 'before' to the current item |
| 40 | +predecessors_count_item[item]+=1# Increment the in-degree of the current item |
| 41 | +else:# If the items belong to different groups |
| 42 | +successors_group[before_group].append(current_group)# Add a group dependency |
| 43 | +predecessors_count_group[current_group]+=1# Increment the in-degree of the current group |
| 44 | + |
| 45 | +# Step 4: Perform topological sort on both the group dependencies and item dependencies |
| 46 | +groups_order=self.topologicalSort(successors_group,predecessors_count_group,m)# Topological sort of groups |
| 47 | +items_order=self.topologicalSort(successors_item,predecessors_count_item,n)# Topological sort of items |
| 48 | + |
| 49 | +# Step 5: If there was a cycle detected in either group or item sorting, return an empty list |
| 50 | +ifnotgroups_orderornotitems_order: |
| 51 | +return []# Return an empty list if either the group or item topological sort failed |
| 52 | + |
| 53 | +# Step 6: Group the items based on the group IDs |
| 54 | +items_grouped= [[]for_inrange(m)]# Create an empty list for each group to store its items |
| 55 | +foriteminitems_order:# Process each item in topologically sorted order |
| 56 | +items_grouped[group[item]].append(item)# Add the item to the appropriate group |
| 57 | + |
| 58 | +# Step 7: Combine the groups in topologically sorted order |
| 59 | +result= []# The final result list to store the sorted items |
| 60 | +forgrpingroups_order:# For each group in topologically sorted order |
| 61 | +result.extend(items_grouped[grp])# Add the items of the group to the result |
| 62 | + |
| 63 | +returnresult# Return the final sorted list of items respecting both item and group dependencies |