Sort Items By Group

Posted: 9 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given ‘N’ items. Each item either doesn’t belong to any group or belongs to exactly one group out of ‘M’ groups. For each item, you are also given a list, ‘BEFORE’, containing items that should appear before this item in the final sorted list.

Your task is to sort these items in an order which follows the following rules :

The items belonging to the same group must be ordered adjacent to each other.
The item which does not belong to any group can be placed anywhere. 
Each item appearing in BEFORE[i] must be placed before the ith item in the sorted list.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of items and the number of groups respectively. 

The second line of each test case contains ‘N’ space-separated integers, where every ith integer denotes the group to which the ith item belongs. If an item does not belong to any group, “-1” is used at its place.

Then ‘N’ lines follow, and each of these lines contains the following :

An integer ‘X’ denoting the number of items that should be placed before the ith item. Then X space-separated integers follow. Each integer, ‘Y’ denotes the item number that should be placed before the ith item
Output Format :
For each test case, print ‘N’ space-separated integers, denoting the items in the required order.

If there is no order of items that can match all the requirements, print a single integer “-1”.

Output for each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N,M <= 10^5
-1 <= GROUP[I] <= M-1
0 <= X <= N-1
0 <= Y <= N-1

Where ‘GROUP[i]’ is the group to which the ith item belongs.

Time Limit: 1 sec
Approach 1

Approach:

 

The approach is to use Topological Sorting to find the required sorted order of groups and also the required sorted order of items within each group. We can assume that each item that does not belong to any group is a part of a new group. Then we can use Topological Sort to sort the groups first. Then we can sort the items within each group. While using Topological Sorting, if we find a cycle in the graph, then we can safely say that there can never be an order of items that can match all the requirements and we can simply print “-1”. 

 

Steps:

 

  1. Run a loop from i=0 to i<numOfItems, and do:
    1. If the ith item does not belong to any group we make group[i] = numOfGroups, and increase numOfGroups by 1.
  2. Create a vector, say groupDependency of size numOfGroups to store the group dependencies.
  3. Run a loop from i=0 to i<numOfItems, and do:
    1. For each item j in before[i], 
      1. If group[i] == group[j], continue. This is because if the groups of both these items are the same, then we don't have to consider that because order of items in a group doesn't matter
      2. Push group[j] in groupDependency[group[i]].
  4. Initialize a variable, say cyclePresent = false. This will keep track of cycle in the graph.
  5. Declare a vector, say itemsSort to store the sorting result of topSort(numOfItems, before, cyclePresent).
  6. Declare a vector, say groupsSort to store the sorting result of topSort(numOfGroups, groupDependency, cyclePresent).
  7. If cyclePresent = true, that means that there is a cycle present in this graph and thus there can not be any order of items that matches all the requirements so we create a vector containing a single integer “-1” and return it.
  8. Now, define a Lambda function. A Lambda function allows us to write inline functions by accessing variables from the surrounding scope. Our Lambda function will sort items in the following way:
    1. If two items have the same group, then the item appearing first in itemsSort comes first.
    2. If the groups are different, then the item which belongs to the first appearing group in groupsSort comes first.
  9. Now, create a vector, say sortedItems, of size numOfItems. Run a loop from i=0 to i<numOfItems and make sortedItems[i] = i.
  10. Now Sort these items according to the lambda function
  11. The sortedItems contains all the items in the required sorted order. So, we can simply return this vector.
     

vector<int> topSort(num, edges, cyclePresent) {

 

  1. Define a boolean vector, say visited, of size num, and initialize all elements as false. This vector will keep track of all the nodes that have been visited already.
  2. Define a boolean vector, say inCurrentCycle, of size num, and initialize all elements as false. This vector will keep track of all the nodes that are a part of the current cycle.
  3. Initialize a variable, say order=0, to mark the order of the current cycle.
  4. Define a vector, say sortedOrder, of size num, to store elements in the sorted order.
  5. Run a loop from i=0 to i<num and do:
    1. If cyclePresent, return an empty vector.
    2. If ith element has not been visited, then call findOrder(i, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).
  6. Return sortedOrder.  

 

Void findOrder(i, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent) {

 

  1. If the current node is a part of the current cycle, make cyclePresent as true and return. If the current node has been already visited, then simply return.
  2. Now, make visited[i]=true and make inCurrentCycle[i] = true.
  3. For every j in edges[i], do:
    1. If cyclePresent, return.
    2. Recursively call findOrder(j, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).
  4. Now, since we have completely traversed the current cycle, so the current node is not a part of the new cycle that we will traverse next. Hence, make inCurrentCycle[i]=false.
  5. Make sortedOrder[i] = order. This is because all the elements of the current cycle have been given the same order.
  6. Increase the order by 1 for the next cycle.
Try Problem