Source code for submission s1124

Go to diff to previous submission

Fn.java

  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5.  
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.HashMap;
  9. import java.util.HashSet;
  10. import java.util.LinkedList;
  11. import java.util.List;
  12. import java.util.Map;
  13. import java.util.Scanner;
  14. import java.util.Set;
  15.  
  16. /**
  17.  *
  18.  * @author cteam92
  19.  */
  20. public class Fn {
  21.  
  22. static ArrayList<LinkedList<Integer>> graph;
  23. static int n, m;
  24. static boolean[] visited;
  25. static int[] components;
  26.  
  27. static void markComponents() {
  28. components = new int[n];
  29. // visited = new boolean[n];
  30. // for (int i = 0; i < n; i++) {
  31. // dfs(i, i);
  32. // }
  33.  
  34. }
  35.  
  36. static void dfs(int node, int leader) {
  37. if (visited[node]) {
  38. return;
  39. }
  40.  
  41. visited[node] = true;
  42. components[node] = leader;
  43. for (Integer neighbour : graph.get(node)) {
  44. dfs(neighbour, leader);
  45. }
  46.  
  47. }
  48.  
  49. public static void main(String[] args) {
  50. Scanner sc = new Scanner(System.in);
  51. while (true) {
  52. int V1, V2;
  53.  
  54. if (!sc.hasNext()) {
  55. break;
  56. }
  57.  
  58. n = sc.nextInt();
  59. m = sc.nextInt();
  60. sc.nextLine();
  61.  
  62. graph = new ArrayList<LinkedList<Integer>>();
  63. for (int i = 0; i < n; i++) {
  64. graph.add(new LinkedList<Integer>());
  65. }
  66.  
  67. for (int i = 0; i < m; i++) {
  68. V1 = sc.nextInt();
  69. V2 = sc.nextInt();
  70. sc.nextLine();
  71.  
  72. LinkedList<Integer> vertex;
  73.  
  74. vertex = graph.get(V1 - 1);
  75. vertex.add(V2 - 1);
  76. graph.set(V1 - 1, vertex);
  77.  
  78. vertex = graph.get(V2 - 1);
  79. vertex.add(V1 - 1);
  80. graph.set(V2 - 1, vertex);
  81. }
  82.  
  83. /*System.out.println("----");
  84.   for (int i=0; i<n; i++) {
  85.   System.out.println(graph.get(i).toString());
  86.   }*/
  87. //markComponents();
  88. //System.out.println(Arrays.toString(components));
  89.  
  90. //Set<Integer> withY = new HashSet<Integer>();
  91. Set<Integer> yNodes = new HashSet<Integer>();
  92.  
  93. boolean bunny = false;
  94.  
  95.  
  96. for (int node = 0; node < n; node++) {
  97. int neighbourCount = graph.get(node).size();
  98. if (neighbourCount >= 4) {
  99. bunny = true;
  100. break;
  101. } else if (neighbourCount == 3) {
  102. Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node));
  103.  
  104. for (int i : yNodes) {
  105. Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));
  106.  
  107. //System.out.println("nodeYSet pro " + i + " " + nodeYSet.toString());
  108.  
  109. if (nodeYSet.contains(node)) {
  110. //System.out.println("sousedi" + i + " " + node);
  111. nodeYSet.retainAll(nodeSet);
  112. //System.out.println("po pruniku" + nodeYSet.toString());
  113. if (nodeYSet.isEmpty()) {
  114. //System.out.println("1");
  115. bunny = true;
  116. break;
  117. }
  118. } else {
  119. //System.out.println("nejsou sousedi" + i + " " + node);
  120. nodeYSet.retainAll(nodeSet);
  121. //System.out.println("po pruniku" + nodeYSet.toString());
  122. if (nodeYSet.size() <= 1) {
  123. //System.out.println("2");
  124. bunny = true;
  125. break;
  126. }
  127. }
  128. }
  129. if (bunny) break;
  130. yNodes.add(node);
  131. }
  132. }
  133.  
  134. if (bunny) {
  135. System.out.println("YES");
  136. } else {
  137. System.out.println("NO");
  138. }
  139.  
  140. }
  141.  
  142. }
  143. }
  144.  

Diff to submission s1107

Fn.java

--- c5.s1107.cteam092.fn.java.0.Fn.java
+++ c5.s1124.cteam092.fn.java.0.Fn.java
@@ -85,12 +85,9 @@
              System.out.println(graph.get(i).toString());
              }*/
-            markComponents();
+            //markComponents();
             //System.out.println(Arrays.toString(components));
 
             //Set<Integer> withY = new HashSet<Integer>();
-            Map<Integer, Set<Integer>> yNodes = new HashMap<Integer, Set<Integer>>();
-            for (int i = 0; i < n; i++) {
-                yNodes.put(i, new HashSet<Integer>());
-            }
+            Set<Integer> yNodes = new HashSet<Integer>();
 
             boolean bunny = false;
@@ -105,9 +102,5 @@
                     Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node));
 
-                    if (yNodes.get(components[node]).size() >= 4) {
-                        bunny = true;
-                        break;
-                    }
-                    for (int i : yNodes.get(components[node])) {
+                    for (int i : yNodes) {
                         Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));
                         
@@ -135,5 +128,5 @@
                     }
                     if (bunny) break;
-                    yNodes.get(components[node]).add(node);
+                    yNodes.add(node);
                 }
             }