Source code for submission s1064

Go to diff to previous submission

Fn.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.Scanner;
  4. import java.util.LinkedList;
  5.  
  6.  
  7. /**
  8.  *
  9.  * @author cteam023
  10.  */
  11. public class Fn {
  12.  
  13.  
  14.     private static void vypisVysledek(Kolekce[] pole){
  15.         ArrayList<Integer> trojkovy = new ArrayList<Integer>();
  16.         for (int i = 0; i < pole.length; i++){                                    
  17.             if ( pole[i].s.size()>= 4){
  18.                 System.out.println("YES");
  19.                 return;
  20.             }
  21.             if (pole[i].s.size() == 3){
  22.                 trojkovy.add(i);
  23.             }
  24.         }
  25.  
  26.         if (trojkovy.size() > 1){
  27.             for (int i = 0; i < trojkovy.size(); i++){
  28.                 for (int j = i + 1; j < trojkovy.size(); j++){
  29.                     if (existujeSpojeni(pole, i, j)){
  30.                         System.out.println("YES");
  31.                         return;
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.  
  37.  
  38.  
  39.         System.out.println("NO");
  40.     }
  41.  
  42.     private static boolean existujeSpojeni(Kolekce[] pole, int bod1, int bod2){
  43.         LinkedList<Integer> fronta = new LinkedList<Integer>();
  44.         fronta.addFirst(bod1);
  45.         ArrayList<Integer> expand = new ArrayList<Integer>();
  46.         ArrayList<Integer> closed = new ArrayList<Integer>();
  47.         int tmp;
  48.         while (fronta.size() > 0){
  49.             tmp = fronta.getFirst();
  50.             if (tmp == bod2){
  51.                 return true;
  52.             }
  53.             closed.add(tmp);
  54.             for (Spojeni i: pole[tmp].s){
  55.                 expand.add(i.getDruhy(tmp));                
  56.             }
  57.             expand.removeAll(closed);
  58.             expand.removeAll(fronta);
  59.             fronta.removeLast();
  60.             fronta.addAll(expand);
  61.         }
  62.  
  63.         return false;
  64.  
  65.  
  66.     }
  67.  
  68.     public static void main(String[] args) {
  69.         Scanner sc = new Scanner(System.in);
  70.         int pocetBodu, pocetCar;
  71.         Kolekce[] pole;
  72.         int bod1, bod2;
  73.         Spojeni spojeni;
  74.         while(sc.hasNextInt()){
  75.             pocetBodu = sc.nextInt();
  76.             pocetCar = sc.nextInt();
  77.             pole = new Kolekce[pocetBodu];
  78.             for (int i = 0; i < pole.length; i++){
  79.                 pole[i] = new Kolekce();
  80.                 pole[i].s = new ArrayList<Spojeni>();
  81.             }
  82.             for (int i = 0; i < pocetCar; i++){
  83.                 bod1 = sc.nextInt() -1;
  84.                 bod2 = sc.nextInt() -1;
  85.                 spojeni = new Spojeni(bod1, bod2);
  86.                 pole[bod1].s.add(spojeni);
  87.                 pole[bod2].s.add(spojeni);
  88.             }
  89.             vypisVysledek(pole);
  90.         }
  91.     }
  92.  
  93.     private static class Spojeni{
  94.         public int bod1, bod2;
  95.  
  96.         public Spojeni(int bod1, int bod2){
  97.             this.bod1 = bod1;
  98.             this.bod2 = bod2;
  99.         }
  100.  
  101.         public int getDruhy(int bod){
  102.             if(bod == bod1){
  103.                 return bod2;
  104.             }
  105.             return bod1;
  106.         }
  107.  
  108.  
  109.     }
  110.  
  111.     private static class Kolekce{
  112.         public ArrayList<Spojeni> s;
  113.     }
  114.  
  115. }
  116.  

Diff to submission s1059

Fn.java

--- c5.s1059.cteam023.fn.java.0.Fn.java
+++ c5.s1064.cteam023.fn.java.0.Fn.java
@@ -47,5 +47,5 @@
         int tmp;
         while (fronta.size() > 0){
-            tmp = fronta.getLast();
+            tmp = fronta.getFirst();
             if (tmp == bod2){
                 return true;