Hackerrank Solution: Roads and Libraries (Graph Theory)

Problem link from hackerrank

The solution is given below with the introduction of DFS.

Introduction:

Algorithm: DFS (Depth First Search) - A graph algorithm.

If you read the problem, you can guess this is a bit advanced problem yet it is very important to learn the algorithm of this problem as early as possible. To solve the problem we have used DFS(Depth First Search) algorithm. This is one of the fundamental algorithms of graph theory. This is needed not only for algorithm courses but also to solve many programming problems. It is also used in other real-life graph related applications.

More info. about DFS in wikipedia. Here is a youtube video for visual understanding.

Now that you have understood the algorithm. I recommend you see the implementation in geeksforgeeks because I've taken the help of this code to solve this interesting problem.

Solution link in GitHub 

Explanation:

After reading the problem and understanding the DFS algorithm from the discussion above, the solution will be much easier to understand. Here the damaged roads are edges and the cities are nodes. A graph may contain several clusters.  A cluster is a set of nodes that are somehow connected to each other (directly or indirectly) but not to other nodes in different clusters.

So each cluster can be considered as a sub-problem / sub-task. The solution for all the clusters will be the final solution. 

A cluster will have at least one library. So the solution will be at least cost_of_library times the number of clusters. After this initial consideration, we are now to decide whether to build a library in each city or to repair the roads of a cluster. If there are 'c' cities in a cluster, there will be c-1 roads.

Now if cost_of_library < cost_of_road, we are better off building c-1 additional libraries in the other c-1 cities adding (c-1)*cost_of_library to our total cost  and if cost_of_library > cost_of_road, we just repair the c-1 roads adding (c-1)*cost_of_road to our total cost.

Now we are to determine the clusters. Here DFS comes into play. We start DFS on non-visited nodes and mark the visited ones. When we start new DFS on a non-visited node, we are traversing a new cluster because previous nodes of other clusters, determined by previous DFS, are unreachable from this new node. After determining the number of nodes in a cluster (using DFSUtil function), we at first add a library's cost and then depending on the condition either add road reparation cost or add additional library cost.

After traversing all the nodes, we have finally determined the optimal cost.