Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1.  
  2. public static String solve2(InputStream in){
  3.  
  4. // Read first line of input
  5. int nV = 0;
  6. int mE = 0;
  7. int startV = 0;
  8. int endV = 0;
  9. Scanner sc = new Scanner(in);
  10.  
  11. if(sc.hasNextLine()){
  12. nV = sc.nextInt();
  13. mE = sc.nextInt();
  14. startV = sc.nextInt();
  15. endV = sc.nextInt();
  16. }
  17.  
  18. // Create the Node List
  19. Node[] list = readData2(sc, nV);
  20. sc.close();
  21. if (mE == 0) return "no";
  22. if (nV == 0) return "no";
  23. if (startV==endV) return "yes";
  24. Node startNode = list[startV-1];
  25. Node endNode = list[endV-1];
  26.  
  27. Queue<Node> queue = new LinkedList<>();
  28.  
  29. startNode.marked=true;
  30. queue.offer(startNode);
  31.  
  32. while(queue.size()!=0){
  33. Node current = queue.poll();
  34. if(endNode == current) return "yes";
  35. current.marked = true;
  36.  
  37. for(int i=0; i < current.outEdges.size();i++)
  38. if(current.outEdges.get(i).marked==false) {
  39. current.outEdges.get(i).marked=true;
  40. queue.offer(current.outEdges.get(i));
  41. }
  42. }
  43.  
  44. return "no";
  45. }
  46.  
  47. public static Node[] readData2(Scanner sc, int size){
  48. Node[] list = new Node[size];
  49. while(sc.hasNextLine()){
  50. //get the node
  51. int nodeAt = sc.nextInt() - 1;
  52. int edgeTo = sc.nextInt() - 1;
  53.  
  54. if(list[edgeTo]==null) {
  55. list[edgeTo] = new Node();
  56. }
  57.  
  58. if(list[nodeAt]==null) {
  59. list[nodeAt] = new Node();
  60. }
  61. list[nodeAt].outEdges.add(list[edgeTo]);
  62. // Ignore the rest
  63. sc.nextLine();
  64. }
  65. sc.close();
  66. return list;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement