fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12.         Ideone u = new Ideone();
  13. 	}
  14.  
  15. 	public Map<String, Vertex> miestai = new HashMap<>();
  16.     public List<List<Vertex>> marsrutai = new ArrayList<>();
  17.  
  18.     public Ideone() {
  19.         // sudedam miestus
  20.         miestai.put("Kaunas", new Vertex("Kaunas"));
  21.         miestai.put("Vilnius", new Vertex("Vilnius"));
  22.         miestai.put("Karmelava", new Vertex("Karmelava"));
  23.         miestai.put("Klaipeda", new Vertex("Klaipeda"));
  24.         miestai.put("Siauliai", new Vertex("Siauliai"));
  25.         miestai.put("Panevezys", new Vertex("Panevezys"));
  26.         // sudedam marsrutus
  27.         miestai.get("Kaunas").addMarsrutas(miestai.get("Vilnius"));
  28.         miestai.get("Kaunas").addMarsrutas(miestai.get("Siauliai"));
  29.         miestai.get("Kaunas").addMarsrutas(miestai.get("Klaipeda"));
  30.         miestai.get("Vilnius").addMarsrutas(miestai.get("Kaunas"));
  31.         miestai.get("Vilnius").addMarsrutas(miestai.get("Karmelava"));
  32.         miestai.get("Karmelava").addMarsrutas(miestai.get("Kaunas"));
  33.         miestai.get("Karmelava").addMarsrutas(miestai.get("Klaipeda"));
  34.         miestai.get("Klaipeda").addMarsrutas(miestai.get("Vilnius"));
  35.         miestai.get("Klaipeda").addMarsrutas(miestai.get("Siauliai"));
  36.         miestai.get("Siauliai").addMarsrutas(miestai.get("Panevezys"));
  37.  
  38.         // paieska
  39.         getMarsrutai("Vilnius", "Panevezys");
  40.  
  41.         // tikrinam rezultatus
  42.         for (int i = 0; i < marsrutai.size(); i++) {
  43.             for (int j = 0; j < marsrutai.get(i).size(); j++) {
  44.                 System.out.print(marsrutai.get(i).get(j).vardas + " ");
  45.             }
  46.             System.out.println();
  47.         }
  48.     }
  49.  
  50.     // paieska
  51.     public void getMarsrutai(String fromName, String toName) {
  52.         Vertex from = miestai.get(fromName);
  53.         Vertex to = miestai.get(toName);
  54.  
  55.         Stack<Vertex> visited = new Stack<>();
  56.         visited.add(from);
  57.  
  58.         Queue<Vertex> toVisit = new LinkedList<>(from.marsrutai); // pasiekiami miestai is esamo miesto
  59.         while (toVisit.peek() != null) {
  60.             getMarsrutai(toVisit.poll(), to, visited);
  61.         }
  62.     }
  63.  
  64.     /**
  65.      * Rekursija
  66.      * @param from Dabartine stotis
  67.      * @param to Tikslas
  68.      * @param visited Aplankytos stoteles
  69.      */
  70.     public void getMarsrutai(Vertex from, Vertex to, Stack<Vertex> visited) {
  71.         if (from.equals(to)) { // pasiekeme tiksla
  72.             visited.add(from);
  73.             marsrutai.add(new ArrayList<>(visited));
  74.             visited.pop();
  75.             return;
  76.         }
  77.  
  78.         if (visited.contains(from)) { // apsauga nuo begalinio ciklo
  79.             return;
  80.         }
  81.  
  82.         visited.add(from); // idedamam esama vieta i aplankytu sarasa
  83.         Queue<Vertex> toVisit = new LinkedList<>(from.marsrutai); // pasiekiami miestai is esamo miesto
  84.         while (toVisit.peek() != null) {
  85.             getMarsrutai(toVisit.poll(), to, visited);
  86.         }
  87.  
  88.         visited.pop(); // isimam, kad vel galetume pasiekti si miesta
  89.     }
  90.  
  91.     class Vertex {
  92.         String vardas;
  93.         List<Vertex> marsrutai = new ArrayList<>();
  94.  
  95.         public Vertex(String vardas) {
  96.             this.vardas = vardas;
  97.         }
  98.  
  99.         public void addMarsrutas(Vertex m) {
  100.             marsrutai.add(m);
  101.         }
  102.     }
  103. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
Vilnius Kaunas Siauliai Panevezys 
Vilnius Kaunas Klaipeda Siauliai Panevezys 
Vilnius Karmelava Kaunas Siauliai Panevezys 
Vilnius Karmelava Kaunas Klaipeda Siauliai Panevezys 
Vilnius Karmelava Klaipeda Siauliai Panevezys
https://ideone.com/SHQowd
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!