Goldman Sachs OA problem

Round 1

Questions: Anaximander was a Greek traveller who visited many countries during his lifetime. He left behind a vivid description of the countries he visited in the form of a graph where each node represents a city and the edges represent the roads between them.

It is also known that all the cities of a country are directly connected to each other through bidirectional roads. Some other interesting features of these countries were that there were at least 3 cities in each country, with exactly one road between any two countries and it was possible to start the journey from one country and visit any other country.

With the help of the above information, you need to determine the number of countries that Anaximander visited.

Input Format: The first line of the input contains one integer T - the number of test cases. Then T test cases follow.

The first line of each test case contains 2 space-separated integers N and M - the total number of cities and roads respectively.

The next M lines contain 2 space-separated integers - Ui and Vi representing the cities at the ends of the ith bidirectional road.

Output Format: For each test case, print on a new line the number of countries visited by Anaximander.

Constraints: 1 <= T <= 100

3 <= N <= 1000

1 <= Ui, Vi <= N

It's guaranteed that the sum of N over all test cases <= 1000 and there are no self edges or multiple edges in the graph.

Hints to Solve the Problem:

• You can represent the cities and roads as a graph using an adjacency list or matrix.
• To determine the number of countries, you need to find the connected components in the graph.
• You can use Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph and count the number of connected components.
• Each connected component corresponds to a country.