Friday, 16 June 2017

Graph Problem based on Traversal (DFS) | Hackerrank : Roads and Libraries

Hello Friends,

I am here with an problem based on Graphs. This I took from Hacker rank

The Problem summary is as follows.

Input and the problem Summary
  1. There are n cites. 
  2. Each city must either have a library or  be connected directly or indirectly via another city to a city having a library.
  3. There are only m roads which can be build. These m paths are provided in the questions and represented by pair (city1,city2) : path connecting city1 and city2 directly.
  4.  Cost of building the library is given as a part of input. (Big number between 1 and 10^5)
  5. Cost of building road between any two cities is constant and is also given as a part of input.
    (Big number between 1 and 10^5)

Minimum cost to make each city accessible to Library. 

Here is the code in Java for above problem:

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(;
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            int m = in.nextInt();
            long x = in.nextLong(); // lib
            long y = in.nextLong(); // road
            Graph g = new Graph(n,m,x,y);
            for(int a1 = 0; a1 < m; a1++){
                int city_1 = in.nextInt();
                int city_2 = in.nextInt();
        public static class Graph{
            long costRoad;
            long costLib;
            int n,m;
            Graph(int n, int m , long costLib, long costRoad){
                this.costRoad = costRoad;
                this.costLib = costLib;
                this.n = n;
                this.m = m;
            private static class Node{
                Integer name;
                AdjListNode listHead;
                boolean isVisited;
                public Node(Integer name){
           = name;
            private static class AdjListNode{
                AdjListNode next;
                Node adj;
                AdjListNode(Node adj, AdjListNode next){
                    this.adj = adj;
           = next;
            Map<Integer,Node> nameNodeMap = new HashMap<>();
            void addEdge(Integer c1, Integer c2){
                Node n1 = nameNodeMap.get(c1);
                Node n2 = nameNodeMap.get(c2);
                n1.listHead = new AdjListNode(n2,n1.listHead);
                n2.listHead = new AdjListNode(n1,n2.listHead);
            void addSingleNodes(){
                for(Integer i = 1; i <= n; i++){
                   nameNodeMap.put(i,new Node(i));
            long computeCost(){
               long answer = 0;
               if(costLib <= costRoad){
                   answer = n*costLib;
                   return answer;
               for(Node node : nameNodeMap.values()){
                       answer += dfs(node)-costRoad + costLib;
               return answer;
            long dfs(Node node){
                AdjListNode temp = node.listHead;
                long cost = costRoad; 
                node.isVisited = true;
                while(temp != null){
                       cost += dfs(temp.adj);
                    temp =;       
                return cost;


 ** Make Sure we initialize all the vertices (nodes) of the graph. This should be independent of edge adding logic as the input edges may not contain all the vertices , there may be nodes which are not connected to any other vertices.