DIFFICULTY:
MEDIUM
PREREQUISITES:
Graph, DFS
PROBLEM:
Technoland is a country made up of many islands. One of the Island is attacked by a group of terrorists. In one Island, there is an undirected path from every city to other city. However the rescue team is not able to reach the desired island as there is no path between two islands. Identify the different islands in techno land and find the minimum number of edges to be added so that we can reach from every island to every other island.
An island is represented by connected nodes in the graph.
QUICK EXPLANATION:
There are nodes connected to each other as indicated by the edges present in the graph. Nodes which are connected to each other form an island. The given input will have such set of islands. The number of islands-1 will give the minimum number of edges to be added in the graph to connect all islands.
EXPLANATION:
Consider a graph as given in the sample input. The given input has three islands. Hence, as shown 3-1 = 2 edges need to be added to connect all the 3 islands to each other.
This can be easily achieved by identifying the number of islands. For this we can run a Depth first search starting at any randomly selected node. On running DFS, if we stop before all nodes are visited, we have found one island. Repeat this process by starting from an unvisited node. The number of times you stop before visiting all given nodes will give the number of islands present.
TIME COMPLEXITY:
If n is the number of nodes, the algorithm should have a complexity of O(n^2)
AUTHOR’S SOLUTION
You can find the solution here