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 https://www.hackerrank.com/challenges/torque-and-development

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)
Output

Minimum cost to make each city accessible to Library. 

Here is the code in Java for above problem:


import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        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);
            g.addSingleNodes();
            for(int a1 = 0; a1 < m; a1++){
                int city_1 = in.nextInt();
                int city_2 = in.nextInt();
                g.addEdge(city_1,city_2);
            }
            System.out.println(g.computeCost());
        }
    }
    
        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){
                    this.name = name;
                }
            }
            private static class AdjListNode{
                AdjListNode next;
                Node adj;
                AdjListNode(Node adj, AdjListNode next){
                    this.adj = adj;
                    this.next = 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()){
                   if(!node.isVisited){
                       answer += dfs(node)-costRoad + costLib;
                   }
               }
               return answer;
            }
            
            long dfs(Node node){
                AdjListNode temp = node.listHead;
                long cost = costRoad; 
                node.isVisited = true;
                while(temp != null){
                    if(!temp.adj.isVisited){
                       cost += dfs(temp.adj);
                    }
                    temp = temp.next;       
                }
                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.