Skip to content

Instantly share code, notes, and snippets.

@rakibulalam
Created May 6, 2020 00:22
Show Gist options
  • Save rakibulalam/11c09b88cb8b6dbbacc338cdb26481dd to your computer and use it in GitHub Desktop.
Save rakibulalam/11c09b88cb8b6dbbacc338cdb26481dd to your computer and use it in GitHub Desktop.
Roads and Libraries Hacker Rank
/*
*/
class Graph{
constructor(n, cost_road,cost_lib)
{
this.size=n;
this.costRoad=cost_road;
this.costLib=cost_lib;
this.adjancies={}
this.visited={};
}
addEdges(x,y)
{
if(!this.adjancies[x])this.adjancies[x]=[];
if(!this.adjancies[y])this.adjancies[y]=[];
this.adjancies[x].push(y);
this.adjancies[y].push(x);
}
connectedGraph()
{
let totalRoadCost=0, totalLibCost=0;
for(let node in this.adjancies)
{
if(!this.visited[node])
{
const result=this.dfs(node);
totalRoadCost+=((result.length-1)*this.costRoad)
totalLibCost+=result.length*this.costLib;
totalRoadCost+=this.costLib;
}
}
const addPrice=(this.size-Object.keys(this.adjancies).length)*this.costLib;
totalRoadCost+=addPrice;
totalLibCost+=addPrice;
return totalRoadCost>=totalLibCost?totalLibCost:totalRoadCost;
}
dfs(node, result=[])
{
this.visited[node]=true;
result.push(node);
this.adjancies[node].forEach((neighbor)=>{
if(!this.visited[neighbor]) return this.dfs(neighbor, result);
});
return result;
}
}
function roadsAndLibraries(n, c_lib, c_road, cities) {
const graph=new Graph(n,c_road,c_lib);
cities.forEach((value)=>{
graph.addEdges(...value);
});
return graph.connectedGraph();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment