Source code for submission s977

Go to diff to previous submission

Fn.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.HashSet;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.Scanner;
  7. import java.util.Set;
  8.  
  9. public class Fn {
  10.  
  11.     static class Kozel {
  12.  
  13.         public ArrayList<Integer> sousedi = new ArrayList<Integer>();
  14.     }
  15.  
  16.     static Set<Integer> kudylezekozolezec = new HashSet<Integer>();
  17.     static Set<Integer> semnelez = new HashSet<Integer>();
  18.  
  19.     public static void main(String [] args) {
  20.         Scanner scanner = new Scanner(System.in);
  21.         while (scanner.hasNext()) {
  22.             int nodes = scanner.nextInt();
  23.             int edges = scanner.nextInt();
  24.  
  25.             Kozel[] kozelnik = new Kozel[nodes + 1];
  26.             for (int i=1; i<=nodes; i++) {
  27.                 kozelnik[i] = new Kozel();
  28.             }
  29.  
  30.             for (int i=0; i<edges; i++) {
  31.                 int node1 = scanner.nextInt();
  32.                 int node2 = scanner.nextInt();
  33.                 kozelnik[node1].sousedi.add(node2);
  34.                 kozelnik[node2].sousedi.add(node1);
  35.             }
  36.  
  37.             boolean hasBunny = false;
  38.             for (int i=1; i<=nodes; i++) {
  39.                 if (kozelnik[i].sousedi.size() >= 4) {
  40.                     hasBunny = true;
  41.                     break;
  42.                 } else if (kozelnik[i].sousedi.size() == 3) {
  43.                     hasBunny = prolez(kozelnik, i);
  44.                     if (hasBunny) break;
  45.                 }
  46.             }
  47.             if (hasBunny) {
  48.                 System.out.println("YES");
  49.             } else {
  50.                 System.out.println("NO"); 
  51.             }
  52.  
  53.         }
  54.     }
  55.  
  56.     public static boolean prolez(Kozel[] kozinec, int index) {
  57.  
  58.  
  59.         for (Integer i : kozinec[index].sousedi) {
  60.  
  61.             kudylezekozolezec.clear();
  62.             kudylezekozolezec.add(index);
  63.  
  64.             semnelez.clear();
  65.             for (Integer j : kozinec[index].sousedi) {
  66.                 if (!i.equals(j)) {
  67.                     semnelez.add(j);
  68.                     kudylezekozolezec.add(j);
  69.                 }
  70.             }
  71.  
  72.             if (kozolezec(kozinec, i)) return true;
  73.         }
  74.  
  75.         return false;
  76.     }
  77.  
  78.     public static boolean kozolezec(Kozel[] kozinec, int index) {
  79.  
  80.  
  81.         while (true) {
  82.  
  83.             kudylezekozolezec.add(index);
  84.             int scnt = kozinec[index].sousedi.size();
  85.  
  86.             if (scnt > 3) {
  87.                 return true;
  88.  
  89.             } else {
  90.  
  91.                 int cnt = 0;
  92.  
  93.                 for (int i = 0; i < kozinec[index].sousedi.size(); i++) {
  94.                     if (!semnelez.contains(kozinec[index].sousedi.get(i))) {
  95.                         cnt++;
  96.                     }
  97.                 }
  98.  
  99.                 if (cnt == 3) {
  100.  
  101.                     return true;
  102.  
  103.                 } else if (cnt == 2) {
  104.  
  105.                     boolean nasli = false;
  106.  
  107.                     for (int k = 0; k < kozinec[index].sousedi.size(); k++) {
  108.                         if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(k))) {
  109.                             index = kozinec[index].sousedi.get(k);
  110.                             nasli = true;
  111.                             break;
  112.                         }
  113.                     }
  114.  
  115.                     if (!nasli) return false;
  116.  
  117.  
  118.                 } else {
  119.  
  120.                     return false;
  121.                 }
  122.             }
  123.  
  124.         }
  125.     }
  126.  
  127.  
  128. }
  129.  

Diff to submission s699

Fn.java

--- c5.s699.cteam038.fn.java.0.Fn.java
+++ c5.s977.cteam038.fn.java.0.Fn.java
@@ -15,4 +15,5 @@
     
     static Set<Integer> kudylezekozolezec = new HashSet<Integer>();
+    static Set<Integer> semnelez = new HashSet<Integer>();
 
     public static void main(String [] args) {
@@ -55,8 +56,18 @@
     public static boolean prolez(Kozel[] kozinec, int index) {
         
+        
         for (Integer i : kozinec[index].sousedi) {
-                
+            
             kudylezekozolezec.clear();
             kudylezekozolezec.add(index);
+
+            semnelez.clear();
+            for (Integer j : kozinec[index].sousedi) {
+                if (!i.equals(j)) {
+                    semnelez.add(j);
+                    kudylezekozolezec.add(j);
+                }
+            }
+            
             if (kozolezec(kozinec, i)) return true;
         }
@@ -68,22 +79,48 @@
         
         
-        while (kozinec[index].sousedi.size() == 2) {
+        while (true) {
             
             kudylezekozolezec.add(index);
+            int scnt = kozinec[index].sousedi.size();
             
-            if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(0))) {
-                index = kozinec[index].sousedi.get(0);
-            } else if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(1))) {
-                index = kozinec[index].sousedi.get(1);
+            if (scnt > 3) {
+                return true;
+                
             } else {
-                return false;
+                
+                int cnt = 0;
+                
+                for (int i = 0; i < kozinec[index].sousedi.size(); i++) {
+                    if (!semnelez.contains(kozinec[index].sousedi.get(i))) {
+                        cnt++;
+                    }
+                }
+                
+                if (cnt == 3) {
+                    
+                    return true;
+                    
+                } else if (cnt == 2) {
+                    
+                    boolean nasli = false;
+                    
+                    for (int k = 0; k < kozinec[index].sousedi.size(); k++) {
+                        if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(k))) {
+                            index = kozinec[index].sousedi.get(k);
+                            nasli = true;
+                            break;
+                        }
+                    }
+                    
+                    if (!nasli) return false;
+                    
+                    
+                } else {
+                    
+                    return false;
+                }
             }
+            
         }
-        
-           if (kozinec[index].sousedi.size() > 2) {
-               return true; // to pochopime...
-           } else {
-               return false;
-           }     
     }