Source code for submission s699

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.  
  18. public static void main(String [] args) {
  19. Scanner scanner = new Scanner(System.in);
  20. while (scanner.hasNext()) {
  21. int nodes = scanner.nextInt();
  22. int edges = scanner.nextInt();
  23.  
  24. Kozel[] kozelnik = new Kozel[nodes + 1];
  25. for (int i=1; i<=nodes; i++) {
  26. kozelnik[i] = new Kozel();
  27. }
  28.  
  29. for (int i=0; i<edges; i++) {
  30. int node1 = scanner.nextInt();
  31. int node2 = scanner.nextInt();
  32. kozelnik[node1].sousedi.add(node2);
  33. kozelnik[node2].sousedi.add(node1);
  34. }
  35.  
  36. boolean hasBunny = false;
  37. for (int i=1; i<=nodes; i++) {
  38. if (kozelnik[i].sousedi.size() >= 4) {
  39. hasBunny = true;
  40. break;
  41. } else if (kozelnik[i].sousedi.size() == 3) {
  42. hasBunny = prolez(kozelnik, i);
  43. if (hasBunny) break;
  44. }
  45. }
  46. if (hasBunny) {
  47. System.out.println("YES");
  48. } else {
  49. System.out.println("NO");
  50. }
  51.  
  52. }
  53. }
  54.  
  55. public static boolean prolez(Kozel[] kozinec, int index) {
  56.  
  57. for (Integer i : kozinec[index].sousedi) {
  58.  
  59. kudylezekozolezec.clear();
  60. kudylezekozolezec.add(index);
  61. if (kozolezec(kozinec, i)) return true;
  62. }
  63.  
  64. return false;
  65. }
  66.  
  67. public static boolean kozolezec(Kozel[] kozinec, int index) {
  68.  
  69.  
  70. while (kozinec[index].sousedi.size() == 2) {
  71.  
  72. kudylezekozolezec.add(index);
  73.  
  74. if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(0))) {
  75. index = kozinec[index].sousedi.get(0);
  76. } else if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(1))) {
  77. index = kozinec[index].sousedi.get(1);
  78. } else {
  79. return false;
  80. }
  81. }
  82.  
  83. if (kozinec[index].sousedi.size() > 2) {
  84. return true; // to pochopime...
  85. } else {
  86. return false;
  87. }
  88. }
  89.  
  90.  
  91. }
  92.  

Diff to submission s547

Fn.java

--- c5.s547.cteam038.fn.java.0.Fn.java
+++ c5.s699.cteam038.fn.java.0.Fn.java
@@ -1,8 +1,18 @@
 
+import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Scanner;
+import java.util.Set;
 
 public class Fn {
+    
+    static class Kozel {
+        
+        public ArrayList<Integer> sousedi = new ArrayList<Integer>();
+    }
+    
+    static Set<Integer> kudylezekozolezec = new HashSet<Integer>();
 
     public static void main(String [] args) {
@@ -12,17 +22,24 @@
             int edges = scanner.nextInt();
 
-            int [] poile = new int[nodes + 1];
+            Kozel[] kozelnik = new Kozel[nodes + 1];
+            for (int i=1; i<=nodes; i++) {
+                kozelnik[i] = new Kozel();
+            }
+            
             for (int i=0; i<edges; i++) {
                 int node1 = scanner.nextInt();
                 int node2 = scanner.nextInt();
-                ++poile[node1];
-                ++poile[node2];
+                kozelnik[node1].sousedi.add(node2);
+                kozelnik[node2].sousedi.add(node1);
             }
 
             boolean hasBunny = false;
-            for (int i=0; i<nodes; i++) {
-                if (poile[i] >= 4) {
+            for (int i=1; i<=nodes; i++) {
+                if (kozelnik[i].sousedi.size() >= 4) {
                     hasBunny = true;
                     break;
+                } else if (kozelnik[i].sousedi.size() == 3) {
+                    hasBunny = prolez(kozelnik, i);
+                    if (hasBunny) break;
                 }
             }
@@ -35,4 +52,39 @@
         }
     }
+    
+    public static boolean prolez(Kozel[] kozinec, int index) {
+        
+        for (Integer i : kozinec[index].sousedi) {
+                
+            kudylezekozolezec.clear();
+            kudylezekozolezec.add(index);
+            if (kozolezec(kozinec, i)) return true;
+        }
+        
+        return false;
+    }
+    
+    public static boolean kozolezec(Kozel[] kozinec, int index) {
+        
+        
+        while (kozinec[index].sousedi.size() == 2) {
+            
+            kudylezekozolezec.add(index);
+            
+            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);
+            } else {
+                return false;
+            }
+        }
+        
+           if (kozinec[index].sousedi.size() > 2) {
+               return true; // to pochopime...
+           } else {
+               return false;
+           }     
+    }