Ninja And Fruits

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
Vir Softech

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
4 2
0 2
2 3
5 3
0 1
3 2
1 4
Sample Output 1 :
3
6
Explanation 1 :
For the first test case refer to the example explained above.

For the second test case we have, the number of fruits, N = 5 and the list of pair of fruit ids is { [0, 1], [3, 2], [1, 4] }. From the given list we can say that there are 2 boxes of fruits: [0, 1, 4] and [2, 3]. Therefore Ninja can select two fruits which belong to different boxes as [0, 2], [0, 3], [1, 2], [1, 3], [4, 2], and [4, 3] i.e. a total of 6 ways.
Sample Input 2 :
2
4 1
1 3
6 2
0 2
3 4
Sample Output 2 :
5
13
Hint

Try generating all the possible pairs of fruits and find the pairs which belong to different boxes.

Approaches (2)
Brute Force
  • 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.
  • 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.

Time Complexity

O(N^2 * (N+M)), where ‘N’ and ‘M’ denote the number of fruits and the number of pairs of fruit ids in the list, respectively.

 

We are generating all the possible pairs and for each pair, we check if the two fruits belong to the same box or not, by applying DFS. There are a total of N*(N-1)/2 ~ N^2 pairs and DFS requires O(N+M) time. Also, for each pair, we initialise a visited array, which takes O(N) time. Hence, the overall time complexity is O(N^2 * (N+N+M)) = O(N^2 * (N+M))

Space Complexity

O(N), where ‘N’ is the number of fruits. 

 

Extra space is required for the recursion stack. The maximum depth of the stack can be O(N). We are also making an array ‘visited’ of size N. Hence, the overall space complexity is O(N + N) = O(N).

Code Solution
(100% EXP penalty)
Ninja And Fruits
Full screen
Console