Last Updated: 17 Feb, 2021
Ninja And Fruits
Moderate
Asked in company
Ninja wants to eat some fruits but he has an appetite for only two fruits. There are a total of N fruits where each fruit is labelled with a unique id from 0 to N-1. The fruits are placed in a few boxes and you are given the pairs of fruit ids, where each pair is made up of fruits which are placed in the same box.
Ninja wants to eat only those fruits which are placed in different boxes. Can you find the number of ways Ninja can select two fruits which belong to different boxes?
Example :
Let the number of fruits be 4 i.e. N = 4 and the list of pair of fruit ids be { [0, 2], [2, 3] }. From the given list we can say that there are 2 boxes of fruits: [0, 2, 3] and [1]. Therefore Ninja can select two fruits which belong to different boxes as [1, 0], [1, 2], and [1, 3] i.e. a total of 3 ways.
Input format :
The very first line of input contains an integer T’ denoting the number of test cases.
The first line of every test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of fruits and the number of pairs of fruit ids in the list, respectively.
Each of the next ‘M’ lines contains two space-separated integers ‘u’ and ‘v’ denoting the pairs of fruit ids of the fruits which are placed in the same box.
Output format :
For each test case, print the number of ways Ninja can select two fruits that belong to different boxes.
Output for each test case is printed on a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just return the number of ways.
Constraints :
1 <= T <= 10
2 <= N <= 5 * 10^4
1 <= M < N-1
0 <= Fruit ID <= N-1
Time Limit: 1 sec
Where ‘T’ represents the number of test cases and ‘N’ represents the number of fruits and ‘M’ represents the number of pairs of fruit ids in the list.
Approaches
- A brute force approach could be to generate all the possible pairs of fruits ids. From all these pairs we select only those which contain fruits belonging to different boxes.
- We can easily generate all the possible pairs with the help of two nested loops. A more difficult task is to check if the fruits in the pair belong to different boxes or not.
- This can be done, if we think of the fruit ids as the vertices of a graph and the pairs of ids as an undirected edge connecting these two fruits.
- Now, if a vertex/fruit is reachable from another vertex/fruit, we can say that both of them belong to the same box. Otherwise, they belong to different boxes.
- Reachability of the vertices can be easily checked by applying a DFS traversal from source to destination.
- Hence, for each pair, we apply DFS from one vertex/fruit and check is the other vertex/fruit is reachable or not.
- The number of pairs of vertices which are unreachable from each other gives the number of ways Ninja can select two fruits which belong to different boxes.
Algorithm:
- From the given pairs of fruit ids create an adjacency list considering the fruit ids as vertices and the pairs of ids as an undirected edge.
- Create a variable ans to store the number of ways. Initially ans = 0.
- Loop 1: For i in the range 0 to N-1:
- Loop 2: For j in the range i+1 to N-1:
- Create a visited array of size N and initialize all the entries to false.
- Apply DFS considering ‘i’ as source vertex and ‘j’ as the destination vertex. While performing DFS we keep track of which vertices have been visited by updating the visited array.
- If visited[j] = false, then vertex ‘j’ is unreachable from ‘i’, Hence increment ans by one.
- Loop 2: For j in the range i+1 to N-1:
- Return ans.
Note:
In the above approach, we have used DFS to check reachability. You can also use BFS, but the idea will remain the same.
- We can solve this problem by using the concept of connected components in a graph.
- If we think of the fruits as the vertices of a graph and the pairs of ids as an undirected edge connecting these two fruits then we can say that the fruits in the same box belong to the same connected component.
- The idea is to determine all the connected components along with the number of vertices/fruits in each component. This can be done by applying DFS on all the vertices of the graph.
- We start by applying DFS on node/fruit 0. This will visit all the vertices/fruits which are present in the same box (i.e. belong to the same connected component) as node/fruit 0.
- During the DFS we also keep track of the number of vertices that are visited, which gives us the number of vertices present in the connected component.
- Now, we apply the DFS on the vertices which were not visited before.
- Suppose that the number of connected components in the graph is ‘C’ and the size of the components are S1, S2, ….., Sc. Then the number of ways to select two fruits/vertices which belong to different boxes/connected component can be calculated as:
- Total Number of Ways to select two fruits from N given fruits - Number of ways to select two fruits belonging to the same box.
- (N * (N-1) / 2) - Sigma(Si * (Si-1) / 2) where i belongs to range 1 to C.
Algorithm:
- From the given pairs of fruit ids create an adjacency list considering the fruit ids as vertices and the pairs of ids as an undirected edge.
- Create a variable count to store the number of connected components in the graph. Initialise it with zero.
- Create a visited array of size N and initialize all the entries to false.
- Create another array, componentSizes, to store the sizes of the connected components.
- Loop: For ‘i’ in the range 0 to N-1:
- Apply DFS considering ‘i’ as source vertex. While performing DFS we keep track of which vertices have been visited by updating the visited array. We also keep track of the number of vertices visited in a DFS call.
- Let the number of vertices visited in the current DFS call be ‘S’, this is nothing but the size of the connected component.
- Add ‘S’ to the array componentSizes.
- We have generated a connected component. So, increment the count by 1.
- Create another variable, say ans, to store the number of ways and initialise it with N*(N-1)/2.
- Iterate through the array componentSizes:
- Let the current index be ‘i’.
- Update ans = ans - (componentSizes[i] * (componentSizes[i] - 1) / 2).
- Return ans.
Note:
In the above approach, we have used DFS to find the connected components. You can also use BFS, but the idea will remain the same.