Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package weblab;
- import java.io.*;
- import java.util.*;
- class Node {
- List<Node> outgoingEdges;
- boolean marked;
- public Node() {
- this.outgoingEdges = new ArrayList<>();
- this.marked = false;
- }
- }
- class Solution {
- // Implement the solve method to return the answer to the problem posed by the inputstream.
- public static String run(InputStream in) {
- return new Solution().solve(in);
- }
- public String solve(InputStream in) {
- Scanner scanner = new Scanner(in);
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- int s = scanner.nextInt();
- int t = scanner.nextInt();
- Node[] nodes = new Node[n];
- for(int i = 0; i < n; i++) {
- nodes[i] = new Node();
- }
- for(int j = 0; j < m; j++) {
- int start = scanner.nextInt();
- int end = scanner.nextInt();
- scanner.nextInt();
- nodes[start-1].outgoingEdges.add(nodes[end-1]);
- }
- scanner.close();
- Node start = nodes[s-1];
- Node end = nodes[t-1];
- if(start.equals(end)) return "yes";
- //where your code starts
- Stack<Node> stack = new Stack<Node>();
- stack.push(start);
- while (!stack.empty()){
- Node currNode = stack.pop();
- for (Node node : currNode.outgoingEdges){
- //System.out.println("Node " + currNode.id + " checking edge " + node.id);
- if (node.equals(end)){
- return "yes";
- }
- if(!node.marked)
- stack.push(node);
- node.marked = true;
- }
- //System.out.println("On top of the stack : " + stack.peek().id);
- //System.out.println("Stack empty? " + stack.empty());
- }
- return "no";
- //where your code ends
- }
- // Stack<Node> stack = new Stack<Node>();
- // stack.push(start);
- // start.marked = true;
- // while(stack.size() != 0){
- // Node sblh = stack.pop();
- // for(Node a : sblh.outgoingEdges) {
- // if(a.equals(end)) return "yes";
- // if(!a.marked) stack.push(a);
- // a.marked = true;
- // }
- // }
- // return "no";
- // }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement