Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. package weblab;
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. class Node {
  7.  
  8. List<Node> outgoingEdges;
  9.  
  10. boolean marked;
  11.  
  12. public Node() {
  13. this.outgoingEdges = new ArrayList<>();
  14. this.marked = false;
  15. }
  16. }
  17.  
  18. class Solution {
  19.  
  20. // Implement the solve method to return the answer to the problem posed by the inputstream.
  21. public static String run(InputStream in) {
  22. return new Solution().solve(in);
  23. }
  24.  
  25. public String solve(InputStream in) {
  26.  
  27. Scanner scanner = new Scanner(in);
  28. int n = scanner.nextInt();
  29. int m = scanner.nextInt();
  30. int s = scanner.nextInt();
  31. int t = scanner.nextInt();
  32.  
  33. Node[] nodes = new Node[n];
  34.  
  35. for(int i = 0; i < n; i++) {
  36. nodes[i] = new Node();
  37. }
  38. for(int j = 0; j < m; j++) {
  39. int start = scanner.nextInt();
  40. int end = scanner.nextInt();
  41. scanner.nextInt();
  42. nodes[start-1].outgoingEdges.add(nodes[end-1]);
  43. }
  44. scanner.close();
  45. Node start = nodes[s-1];
  46. Node end = nodes[t-1];
  47. if(start.equals(end)) return "yes";
  48.  
  49. //where your code starts
  50.  
  51. Stack<Node> stack = new Stack<Node>();
  52. stack.push(start);
  53. while (!stack.empty()){
  54. Node currNode = stack.pop();
  55. for (Node node : currNode.outgoingEdges){
  56. //System.out.println("Node " + currNode.id + " checking edge " + node.id);
  57. if (node.equals(end)){
  58. return "yes";
  59. }
  60. if(!node.marked)
  61. stack.push(node);
  62. node.marked = true;
  63.  
  64. }
  65. //System.out.println("On top of the stack : " + stack.peek().id);
  66. //System.out.println("Stack empty? " + stack.empty());
  67. }
  68. return "no";
  69.  
  70. //where your code ends
  71.  
  72. }
  73. // Stack<Node> stack = new Stack<Node>();
  74. // stack.push(start);
  75. // start.marked = true;
  76. // while(stack.size() != 0){
  77. // Node sblh = stack.pop();
  78. // for(Node a : sblh.outgoingEdges) {
  79. // if(a.equals(end)) return "yes";
  80. // if(!a.marked) stack.push(a);
  81. // a.marked = true;
  82. // }
  83. // }
  84.  
  85. // return "no";
  86. // }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement