Source code for submission s973

Fn.java

  1.  
  2. import java.util.*;
  3.  
  4. /**
  5.  *
  6.  * @author cteam039
  7.  */
  8. public class Fn {
  9.  
  10.     public static void main(String... args) {
  11.         int points, lines;
  12.         Scanner scan = new Scanner(System.in);
  13.         while (scan.hasNextInt()) {
  14.             iteration(scan);
  15.  
  16.         }
  17.     }
  18.  
  19.     public static void iteration(Scanner scan) {
  20.         int points, lines;
  21.  
  22.         points = scan.nextInt();
  23.         lines = scan.nextInt();
  24.         List<List<Graph>> graphs = new ArrayList<List<Fn.Graph>>();
  25.         if (points < 2 || lines < 1) {
  26.             System.out.println("NO");
  27.             return;
  28.         }
  29.         for (int i = 0; i < lines; i++) {
  30.             int a = scan.nextInt();
  31.             int b = scan.nextInt();
  32.  
  33.             List<List<Graph>> sets = new ArrayList<List<Graph>>();
  34.             boolean added = false;
  35.             for(List<Graph> graph : graphs){
  36.  
  37.                 added = insert(graph, new Graph(a), new Graph(b));
  38.  
  39.                 if(added){
  40.                     sets.add(graph);
  41.                 }
  42.             }
  43.             if(!added){
  44.                     List<Graph> gr= new ArrayList<Graph>();
  45.                     graphs.add(gr);
  46.                     gr.add(new Graph(a));
  47.                     gr.add(new Graph(b));
  48.             }
  49.             else if(sets.size() > 1) {
  50.                 for(int j = 1; j < sets.size(); j++){
  51.                     for(Graph g : sets.get(j)){
  52.                         if(!sets.get(0).contains(g)){
  53.                             sets.get(0).add(g);
  54.                         }
  55.                     }
  56.                     graphs.remove(sets.get(j));
  57.  
  58.                 }
  59.             }
  60.         }
  61.  
  62.         for(List<Graph> list : graphs){
  63.             int counter = 0;
  64.             for(Graph g: list){
  65.                 if(g.incide == 1){
  66.                     counter ++;
  67.                 }
  68.             }
  69.             if(counter > 3 ){
  70.                 System.out.println("YES");
  71.                 return;
  72.             }
  73.         }
  74.         System.out.println("NO");
  75.  
  76.     }
  77.  
  78.     public static boolean insert(List<Graph> graph, Graph a, Graph b){
  79.         if(graph.contains(a)){
  80.             if(graph.contains(b)){
  81.                 return true;
  82.             }
  83.             else{
  84.                 graph.get(graph.indexOf(a)).incide++;
  85.                 graph.add(b);
  86.                 return true;
  87.             }
  88.         }
  89.         else{
  90.             if(graph.contains(b)){
  91.                 graph.get(graph.indexOf(b)).incide++;
  92.                 graph.add(a);
  93.                 return true;
  94.             }
  95.             else{
  96.                 return false;
  97.             }
  98.         }
  99.     }
  100.  
  101.     private static class Graph {
  102.  
  103.         int id;
  104.         int incide;
  105.  
  106.         public Graph(int id) {
  107.             this.id = id;
  108.             incide = 1;
  109.         }
  110.  
  111.         @Override
  112.         public boolean equals(Object arg0) {
  113.             if(!(arg0 instanceof Graph)){
  114.                 return false;
  115.             }
  116.             return ((Graph)arg0).id == id;
  117.         }
  118.  
  119.         @Override
  120.         public int hashCode() {
  121.             int hash = 5;
  122.             hash = 79 * hash + this.id;
  123.             return hash;
  124.         }
  125.  
  126.  
  127.     }
  128. }
  129.