Ninja hiring test 1

help
1

Pls help and solution :

Ninja has been appointed as a data scientist for a MNC. He has been provided with a huge list of people who belong to some countries. He doesn’t know who belongs to which country, but he knows which two people belong to the same country. Now, he has been asked to find the total number of unique countries this group of people belong to.
Ninja has many other projects to work on, therefore he has passed on this task to you. Are you up to the challenge?
Input Format
First line of input contains two space separated integers representing the total number of people in the group (n) and number of pairs of people § whose country is known to Ninja.
Next p lines contain two integers representing which two people belong to the same country.
Output Format
Print the number of unique countries the given group of people belong to.
Sample Input 1:
4 3
0 1
1 3
0 3
Sample Output 1:
2
Explanation:
Person 0,1 and 3 belong to the same country. No information about person 2 is mentioned. Hence, we can say that person 2 belongs to a separate country than that of person 0,1 and 3. Therefore, there are people from 2 countries in the given group.
Sample Input 2:
6 4
0 1
0 2
1 2
3 4
Sample Output 2:
3

2

This is basically finding the number of connected components in the graph. Make an edge between every 2 nodes and run a dfs. You can also use union find

1 Like
3

You can use DSU for this.

4

No. I counted no of connected components and submitting but it wrong. Why because for
6 4
0 1
0 2
1 2
3 4
No of components is 2 but ans is 3.
My approach is first doing bfs from root, if all nodes visited then ans 1 else count no of components . If any node unvisited and size of adj list ==0 then in finals add +1 to no of components .
But this have wrong ans in 4 test. Pls give correct approach

5

Not clear. Pls explain in detail

6

Check their solutions tab. You will understand.

7

Its correct, we just have to find the number of connected components.

In the example you’ve shown, there are 3 components: [0,1,2] [3,4] [5]

8

hey it is simple problem . You just need to find the number of connected components in undirected graph.

9

Its a simple problem based on DFS. Connected components peoblem.
Google it bro