We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
1) Figure out how to implement a graph.
2) Uses BFS to find minimum distance of each Node from "start". We can use BFS instead of Dijkstra's algorithm since the edges are all the same weight.
importjava.util.Scanner;importjava.util.HashSet;importjava.util.ArrayDeque;publicclassSolution{privatestaticfinalintEDGE_WEIGHT=6;publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intnumQueries=scan.nextInt();for(intq=0;q<numQueries;q++){intnumNodes=scan.nextInt();intnumEdges=scan.nextInt();/* Create Nodes */Node[]node=newNode[numNodes+1];// node "i" will be at index "i"node[0]=null;for(inti=1;i<=numNodes;i++){node[i]=newNode(i);}/* Connect Nodes */for(inti=0;i<numEdges;i++){intn1=scan.nextInt();intn2=scan.nextInt();node[n1].addNeighbor(node[n2]);}/* Create MST */intstart=scan.nextInt();findDistances(node[start]);/* Print results */for(inti=1;i<=numNodes;i++){if(i!=start){System.out.print(node[i].distance+" ");}}System.out.println();}scan.close();}privatestaticvoidfindDistances(Nodestart){if(start==null){return;}ArrayDeque<Node>deque=newArrayDeque<>();// use deque as a queuestart.distance=0;deque.add(start);while(!deque.isEmpty()){Nodecurr=deque.remove();for(Nodeneighbor:curr.neighbors){if(neighbor.distance==-1){// meaning it's unvisitedneighbor.distance=curr.distance+EDGE_WEIGHT;deque.add(neighbor);}}}}/* Implementation of an UNDIRECTED graph */publicstaticclassNode{publicfinalintid;// each Node will have a unique IDpublicintdistance;// Also tells us if Node has been visited (-1 means unvisited)publicHashSet<Node>neighbors;publicNode(intid){this.id=id;distance=-1;neighbors=newHashSet<>();}publicvoidaddNeighbor(Nodeneighbor){neighbors.add(neighbor);neighbor.neighbors.add(this);}@Overridepublicbooleanequals(Objectother){if(other==this){returntrue;}elseif(other==null||!(otherinstanceofNode)){returnfalse;}NodeotherNode=(Node)other;returnthis.id==otherNode.id;}@OverridepublicinthashCode(){returnid;// simple and effective}}}
BFS: Shortest Reach in a Graph
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
General idea:
1) Figure out how to implement a graph.
2) Uses BFS to find minimum distance of each Node from "start". We can use BFS instead of Dijkstra's algorithm since the edges are all the same weight.
From my HackerRank Java solutions.