Source code for submission s1093

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.     static void dfs(int node, int leader) {
  36.         if (visited[node]) {
  37.             return;
  38.         }
  39.  
  40.         visited[node] = true;
  41.         components[node] = leader;
  42.         for (Integer neighbour : graph.get(node)) {
  43.             dfs(neighbour, leader);
  44.         }
  45.  
  46.     }
  47.  
  48.     public static void main(String[] args) {
  49.         Scanner sc = new Scanner(System.in);
  50.         while (true) {
  51.             int V1, V2;
  52.  
  53.             if (!sc.hasNext()) {
  54.                 break;
  55.             }
  56.  
  57.             n = sc.nextInt();
  58.             m = sc.nextInt();
  59.             sc.nextLine();
  60.  
  61.             graph = new ArrayList<LinkedList<Integer>>();
  62.             for (int i = 0; i < n; i++) {
  63.                 graph.add(new LinkedList<Integer>());
  64.             }
  65.  
  66.             for (int i = 0; i < m; i++) {
  67.                 V1 = sc.nextInt();
  68.                 V2 = sc.nextInt();
  69.                 sc.nextLine();
  70.  
  71.                 LinkedList<Integer> vertex;
  72.  
  73.                 vertex = graph.get(V1 - 1);
  74.                 vertex.add(V2 - 1);
  75.                 graph.set(V1 - 1, vertex);
  76.  
  77.                 vertex = graph.get(V2 - 1);
  78.                 vertex.add(V1 - 1);
  79.                 graph.set(V2 - 1, vertex);
  80.             }
  81.  
  82.             /*System.out.println("----");
  83.              for (int i=0; i<n; i++) {
  84.              System.out.println(graph.get(i).toString());
  85.              }*/
  86.             markComponents();
  87.             //System.out.println(Arrays.toString(components));
  88.  
  89.             //Set<Integer> withY = new HashSet<Integer>();
  90.             Map<Integer, Set<Integer>> yNodes = new HashMap<Integer, Set<Integer>>();
  91.             for (int i = 0; i < n; i++) {
  92.                 yNodes.put(i, new HashSet<Integer>());
  93.             }
  94.  
  95.             boolean bunny = false;
  96.  
  97.  
  98.             for (int node = 0; node < n; node++) {
  99.                 int neighbourCount = graph.get(node).size();
  100.                 if (neighbourCount >= 4) {
  101.                     bunny = true;
  102.                     break;
  103.                 } else if (neighbourCount == 3) {
  104.                     Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node));
  105.  
  106.                     if (yNodes.get(components[node]).size() >= 4) {
  107.                         bunny = true;
  108.                         break;
  109.                     }
  110.                     for (int i : yNodes.get(components[node])) {
  111.                         Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));
  112.  
  113.                         //System.out.println("nodeYSet pro " + i + " " + nodeYSet.toString());
  114.  
  115.                         if (nodeYSet.contains(node)) {
  116.                             //System.out.println("sousedi" + i + " " + node);
  117.                             nodeYSet.retainAll(nodeSet);
  118.                             //System.out.println("po pruniku" + nodeYSet.toString());
  119.                             if (nodeYSet.isEmpty()) {
  120.                                 //System.out.println("1");
  121.                                 bunny = true;
  122.                                 break;
  123.                             }
  124.                         } else {
  125.                             //System.out.println("nejsou sousedi" + i + " " + node);
  126.                             nodeYSet.retainAll(nodeSet);
  127.                             //System.out.println("po pruniku" + nodeYSet.toString());
  128.                             if (nodeYSet.size() <= 1) {
  129.                                 //System.out.println("2");
  130.                                 bunny = true;
  131.                                 break;
  132.                             }
  133.                         }
  134.                     }
  135.                     if (bunny) break;
  136.                     yNodes.get(components[node]).add(node);
  137.                 }
  138.             }
  139.  
  140.             if (bunny) {
  141.                 System.out.println("YES");
  142.             } else {
  143.                 System.out.println("NO");
  144.             }
  145.  
  146.         }
  147.  
  148.     }
  149. }
  150.  

Diff to submission s1062

Fn.java

--- c5.s1062.cteam092.fn.java.0.Fn.java
+++ c5.s1093.cteam092.fn.java.0.Fn.java
@@ -104,4 +104,8 @@
                     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])) {
                         Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));