Source code for submission s1107

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.             Map<Integer, Set<Integer>> yNodes = new HashMap<Integer, Set<Integer>>();
  92.             for (int i = 0; i < n; i++) {
  93.                 yNodes.put(i, new HashSet<Integer>());
  94.             }
  95.  
  96.             boolean bunny = false;
  97.  
  98.  
  99.             for (int node = 0; node < n; node++) {
  100.                 int neighbourCount = graph.get(node).size();
  101.                 if (neighbourCount >= 4) {
  102.                     bunny = true;
  103.                     break;
  104.                 } else if (neighbourCount == 3) {
  105.                     Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node));
  106.  
  107.                     if (yNodes.get(components[node]).size() >= 4) {
  108.                         bunny = true;
  109.                         break;
  110.                     }
  111.                     for (int i : yNodes.get(components[node])) {
  112.                         Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));
  113.  
  114.                         //System.out.println("nodeYSet pro " + i + " " + nodeYSet.toString());
  115.  
  116.                         if (nodeYSet.contains(node)) {
  117.                             //System.out.println("sousedi" + i + " " + node);
  118.                             nodeYSet.retainAll(nodeSet);
  119.                             //System.out.println("po pruniku" + nodeYSet.toString());
  120.                             if (nodeYSet.isEmpty()) {
  121.                                 //System.out.println("1");
  122.                                 bunny = true;
  123.                                 break;
  124.                             }
  125.                         } else {
  126.                             //System.out.println("nejsou sousedi" + i + " " + node);
  127.                             nodeYSet.retainAll(nodeSet);
  128.                             //System.out.println("po pruniku" + nodeYSet.toString());
  129.                             if (nodeYSet.size() <= 1) {
  130.                                 //System.out.println("2");
  131.                                 bunny = true;
  132.                                 break;
  133.                             }
  134.                         }
  135.                     }
  136.                     if (bunny) break;
  137.                     yNodes.get(components[node]).add(node);
  138.                 }
  139.             }
  140.  
  141.             if (bunny) {
  142.                 System.out.println("YES");
  143.             } else {
  144.                 System.out.println("NO");
  145.             }
  146.  
  147.         }
  148.  
  149.     }
  150. }
  151.  

Diff to submission s1093

Fn.java

--- c5.s1093.cteam092.fn.java.0.Fn.java
+++ c5.s1107.cteam092.fn.java.0.Fn.java
@@ -27,8 +27,9 @@
     static void markComponents() {
         components = new int[n];
-        visited = new boolean[n];
-        for (int i = 0; i < n; i++) {
-            dfs(i, i);
-        }
+//        visited = new boolean[n];
+//        for (int i = 0; i < n; i++) {
+//            dfs(i, i);
+//        }
+        
     }