# Sort Items By Group

Posted: 9 Apr, 2021

Difficulty: Moderate

#### 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:**

- Run a loop from
**i=0**to**i<numOfItems**, and do:- If the ith item does not belong to any group we make
**group[i] = numOfGroups,**and increase**numOfGroups**by 1.

- If the ith item does not belong to any group we make
- Create a vector, say
**groupDependency**of size**numOfGroups**to store the group dependencies. - Run a loop from
**i=0**to**i<numOfItems,**and do:- For each item
**j**in**before[i],**- 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 - Push
**group[j]**in**groupDependency[group[i]].**

- If

- For each item
- Initialize a variable, say
**cyclePresent**=**false.**This will keep track of cycle in the graph. - Declare a vector, say
**itemsSort**to store the sorting result of**topSort(numOfItems, before, cyclePresent).** - Declare a vector, say
**groupsSort**to store the sorting result of**topSort(numOfGroups, groupDependency, cyclePresent).** - 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. - 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:
- If two items have the same group, then the item appearing first in
**itemsSort**comes first. - If the groups are different, then the item which belongs to the first appearing group in
**groupsSort**comes first.

- If two items have the same group, then the item appearing first in
- Now, create a vector, say
**sortedItems,**of size**numOfItems.**Run a loop from**i=0**to**i<numOfItems**and make**sortedItems[i] = i.** - Now Sort these items according to the lambda function
- The
**sortedItems**contains all the items in the required sorted order. So, we can simply return this vector.

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

- 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. - 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. - Initialize a variable, say
**order=0,**to mark the order of the current cycle. - Define a vector, say
**sortedOrder,**of size**num,**to store elements in the sorted order. - Run a loop from
**i=0**to**i<num**and do:- If
**cyclePresent,**return an empty vector. - If ith element has not been visited, then call
**findOrder(i, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).**

- If
- Return
**sortedOrder.**

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

- 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. - Now, make
**visited[i]=true**and make**inCurrentCycle[i] = true.** - For every
**j**in**edges[i],**do:- If
**cyclePresent,**return. - Recursively call
**findOrder(j, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).**

- If
- 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.** - Make
**sortedOrder[i] = order.**This is because all the elements of the current cycle have been given the same order. - Increase the
**order**by 1 for the next cycle.

SIMILAR PROBLEMS

# Get DFS Path

Posted: 22 Jul, 2021

Difficulty: Easy

# Get Path using BFS

Posted: 22 Jul, 2021

Difficulty: Easy

# Bellman Ford

Posted: 23 Jul, 2021

Difficulty: Moderate

# Floyd Warshall

Posted: 23 Jul, 2021

Difficulty: Moderate

# Collect Maximum Coins in Matrix

Posted: 29 Oct, 2021

Difficulty: Moderate