Source code for submission s1120

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. package test;
  7.  
  8. import java.util.HashSet;
  9. import java.util.LinkedList;
  10. import java.util.Scanner;
  11. import java.util.Set;
  12. import java.util.TreeSet;
  13.  
  14. /**
  15.  *
  16.  * @author cteam043
  17.  */
  18. public class Fn {
  19.  
  20.     static class Node{
  21.         LinkedList<Integer> children;
  22.         int state;
  23.         int number;
  24.         int comp;
  25.  
  26.         public Node() {
  27.             children = new LinkedList<Integer>();
  28.         }
  29.  
  30.     }
  31.  
  32.     static class Edge{
  33.         int from, to;
  34.  
  35.         public Edge(int from, int to) {
  36.             this.from = from;
  37.             this.to = to;
  38.         }
  39.  
  40.         @Override
  41.         public boolean equals(Object obj) {
  42.             if (obj == null) {
  43.                 return false;
  44.             }
  45.             if (getClass() != obj.getClass()) {
  46.                 return false;
  47.             }
  48.             final Edge other = (Edge) obj;
  49.             if (this.from == other.to && this.to == other.from) {
  50.                 return true;
  51.             }
  52.             if (this.from != other.from || this.to != other.from) {
  53.                 return false;
  54.             }
  55.             if (this.to != other.to || this.from != other.to) {
  56.                 return false;
  57.             }
  58.             return true;
  59.         }
  60.  
  61.         @Override
  62.         public int hashCode() {
  63.             int hash = 3;
  64.             hash = 89 * hash + this.from + this.to;
  65.             return hash;
  66.         }
  67.  
  68.     }
  69.  
  70.     static void BFS(Node start, Set<Integer> from){
  71.         LinkedList<Integer> q = new LinkedList<Integer>();
  72.  
  73.         q.add(start.number);
  74.         while(!q.isEmpty()){
  75.             int tmp = q.getFirst();
  76.             q.pollFirst();
  77.             if(from.contains(tmp))
  78.                 from.remove(tmp);
  79.             else
  80.                 continue;
  81.  
  82.             for(int n : uzly[tmp].children){
  83.                 q.add(n);
  84.             }
  85.         }
  86.     }
  87.  
  88.     static boolean Kostra(Node start){
  89.         HashSet<Edge> ns = new HashSet<Edge>();
  90.         LinkedList<Integer> q = new LinkedList<Integer>();
  91.         HashSet<Integer> set = new HashSet<Integer>();
  92.  
  93.         q.add(start.number);
  94.         while(!q.isEmpty()){
  95.             Integer f = q.getFirst();
  96.             q.pollFirst();
  97.             set.add(f);
  98.             for (Integer integer : uzly[f].children) {
  99.                 if(uzly[integer].state == 0){
  100.                     uzly[integer].state = 1;
  101.                     q.push(integer);
  102.                     ns.add(new Edge(f, integer));
  103.                 }
  104.             }
  105.         }
  106.  
  107.         for(Edge e : ns){
  108.             stupne[e.from]++;
  109.             stupne[e.to]++;
  110.         }
  111.         int res = 0;
  112.         for(Integer i : set){
  113.             if(stupne[i] == 1)
  114.                 res++;
  115.         }
  116.         if(res >= 4)
  117.             return true;
  118.         else
  119.             return false;
  120.  
  121.     }
  122.  
  123.     static Node [] uzly = new Node[10005];
  124.     static{
  125.         for(int i = 0; i < uzly.length; i++){
  126.             uzly[i] = new Node();
  127.             uzly[i].number = i;
  128.         }
  129.     }
  130.     static int [] stupne = new int [10005];
  131.     //static int [][] inci = new int[10005][10005];
  132.  
  133.     public static void main(String[] args) {
  134.  
  135.         boolean bEnd;
  136.         Scanner in = new Scanner(System.in);
  137.         int points, lines, n1, n2;
  138.  
  139.  
  140.         TreeSet<Integer> set = new TreeSet<Integer>();
  141.         LinkedList<Integer> comps = new LinkedList<Integer>();
  142.  
  143.  
  144.         while(in.hasNextInt()){
  145.             bEnd = false;
  146.             points = in.nextInt();
  147.             lines = in.nextInt();
  148.             set.clear();
  149.             comps.clear();
  150.  
  151.             for(int p = 0; p < stupne.length; p++){
  152.                 stupne[p] = 0;
  153.  
  154.                 uzly[p].children.clear();
  155.                 uzly[p].state = 0;
  156.                 uzly[p].comp = 0;
  157.             }
  158.  
  159. //            for(int k = 0; k < stupne.length; k++)
  160. //                for(int l = 0; l < stupne.length; l++)
  161. //                    inci[k][l] = 0;
  162.  
  163.             for(int i = 0; i < lines; i++){
  164.                 n1 = in.nextInt();
  165.                 n2 = in.nextInt();
  166.                 uzly[n1].children.add(n2);
  167.                 uzly[n2].children.add(n1);
  168.                 set.add(n1);
  169.                 set.add(n2);
  170.             }
  171.             int i = 1;            
  172.             while(set.size() != 0){
  173.                 comps.add(set.first());
  174.                 //System.out.println("Comp " + i + " " +set.first());
  175.                 BFS(uzly[set.first()], set);
  176.  
  177.             }
  178.  
  179.             for(Integer g : comps){
  180.                 if(Kostra(uzly[g])){
  181.                     System.out.println("YES");
  182.                     bEnd = true;
  183.                     break;
  184.                 }
  185.             }
  186.             if(!bEnd)
  187.                 System.out.println("NO");
  188.  
  189.         }
  190.     }
  191.  
  192. }
  193.  
  194.  

Diff to submission s693

Fn.java

--- c5.s693.cteam043.fn.java.0.Fn.java
+++ c5.s1120.cteam043.fn.java.0.Fn.java
@@ -4,7 +4,11 @@
  */
 
-package basic;
+package test;
 
+import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.Scanner;
+import java.util.Set;
+import java.util.TreeSet;
 
 /**
@@ -14,30 +18,173 @@
 public class Fn {
     
+    static class Node{
+        LinkedList<Integer> children;
+        int state;
+        int number;
+        int comp;
+
+        public Node() {
+            children = new LinkedList<Integer>();
+        }
+
+    }
+    
+    static class Edge{
+        int from, to;
+
+        public Edge(int from, int to) {
+            this.from = from;
+            this.to = to;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj == null) {
+                return false;
+            }
+            if (getClass() != obj.getClass()) {
+                return false;
+            }
+            final Edge other = (Edge) obj;
+            if (this.from == other.to && this.to == other.from) {
+                return true;
+            }
+            if (this.from != other.from || this.to != other.from) {
+                return false;
+            }
+            if (this.to != other.to || this.from != other.to) {
+                return false;
+            }
+            return true;
+        }
+
+        @Override
+        public int hashCode() {
+            int hash = 3;
+            hash = 89 * hash + this.from + this.to;
+            return hash;
+        }
+                
+    }
+    
+    static void BFS(Node start, Set<Integer> from){
+        LinkedList<Integer> q = new LinkedList<Integer>();
+        
+        q.add(start.number);
+        while(!q.isEmpty()){
+            int tmp = q.getFirst();
+            q.pollFirst();
+            if(from.contains(tmp))
+                from.remove(tmp);
+            else
+                continue;
+            
+            for(int n : uzly[tmp].children){
+                q.add(n);
+            }
+        }
+    }
+    
+    static boolean Kostra(Node start){
+        HashSet<Edge> ns = new HashSet<Edge>();
+        LinkedList<Integer> q = new LinkedList<Integer>();
+        HashSet<Integer> set = new HashSet<Integer>();
+        
+        q.add(start.number);
+        while(!q.isEmpty()){
+            Integer f = q.getFirst();
+            q.pollFirst();
+            set.add(f);
+            for (Integer integer : uzly[f].children) {
+                if(uzly[integer].state == 0){
+                    uzly[integer].state = 1;
+                    q.push(integer);
+                    ns.add(new Edge(f, integer));
+                }
+            }
+        }
+  
+        for(Edge e : ns){
+            stupne[e.from]++;
+            stupne[e.to]++;
+        }
+        int res = 0;
+        for(Integer i : set){
+            if(stupne[i] == 1)
+                res++;
+        }
+        if(res >= 4)
+            return true;
+        else
+            return false;
+        
+    }
+    
+    static Node [] uzly = new Node[10005];
+    static{
+        for(int i = 0; i < uzly.length; i++){
+            uzly[i] = new Node();
+            uzly[i].number = i;
+        }
+    }
+    static int [] stupne = new int [10005];
+    //static int [][] inci = new int[10005][10005];
+    
     public static void main(String[] args) {
         
+        boolean bEnd;
         Scanner in = new Scanner(System.in);
         int points, lines, n1, n2;
-        int [] nodes = new int [10005];
         
+        
+        TreeSet<Integer> set = new TreeSet<Integer>();
+        LinkedList<Integer> comps = new LinkedList<Integer>();
+        
+
         while(in.hasNextInt()){
+            bEnd = false;
             points = in.nextInt();
             lines = in.nextInt();
+            set.clear();
+            comps.clear();
             
-            for(int p = 0; p < nodes.length; p++)
-                nodes[p] = 0;
+            for(int p = 0; p < stupne.length; p++){
+                stupne[p] = 0;
+                
+                uzly[p].children.clear();
+                uzly[p].state = 0;
+                uzly[p].comp = 0;
+            }
+            
+//            for(int k = 0; k < stupne.length; k++)
+//                for(int l = 0; l < stupne.length; l++)
+//                    inci[k][l] = 0;
             
             for(int i = 0; i < lines; i++){
                 n1 = in.nextInt();
                 n2 = in.nextInt();
-                nodes[n1]++;
-                nodes[n2]++;
+                uzly[n1].children.add(n2);
+                uzly[n2].children.add(n1);
+                set.add(n1);
+                set.add(n2);
             }
-            for(int p = 0; p < nodes.length; p++){
-                if(nodes[p] >= 4){
+            int i = 1;            
+            while(set.size() != 0){
+                comps.add(set.first());
+                //System.out.println("Comp " + i + " " +set.first());
+                BFS(uzly[set.first()], set);
+                
+            }
+            
+            for(Integer g : comps){
+                if(Kostra(uzly[g])){
                     System.out.println("YES");
-                    return;
+                    bEnd = true;
+                    break;
                 }
             }
-            System.out.println("NO");
+            if(!bEnd)
+                System.out.println("NO");
+           
         }
     }