Source code for submission s866

Main.java

  1. package javafn;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayDeque;
  6. import java.util.ArrayList;
  7. import java.util.Deque;
  8. import java.util.List;
  9. import java.util.StringTokenizer;
  10.  
  11. public class Main {
  12.  
  13. static StringTokenizer st = new StringTokenizer("");
  14.  
  15. public static void main(String[] args) throws Exception {
  16.  
  17. try {
  18. while (true) {
  19.  
  20. int vertices = Integer.parseInt(nextToken());
  21. int edges = Integer.parseInt(nextToken());
  22.  
  23. int u, v;
  24. Deque<Integer> todo = new ArrayDeque<Integer>();
  25. List<List<Integer>>neigh = new ArrayList<List<Integer>>(vertices + 1);
  26. for (int i = 0; i <= vertices; i++) {
  27. neigh.add(new ArrayList());
  28. neigh.get(i).add(0);//tj counter sousedu
  29. neigh.get(i).add(0);//tj zda uz byl zpracovan
  30. }
  31.  
  32. for (int i = 0; i < edges; i++) {
  33. u = Integer.parseInt(nextToken());
  34. v = Integer.parseInt(nextToken());
  35.  
  36. neigh.get(u).set(0, (neigh.get(u).get(0))+1);
  37. neigh.get(u).add(v);
  38.  
  39. neigh.get(v).set(0, (neigh.get(v).get(0))+1);
  40. neigh.get(v).add(u);
  41. }
  42. int leafesCount;
  43.  
  44.  
  45.  
  46. boolean isYes = false;
  47. for (int i = 1; i < neigh.size(); i++) {
  48. isYes = false;
  49.  
  50. if (neigh.get(i).get(1) == 0) {
  51. todo.push(i);
  52. leafesCount = 0;
  53.  
  54. while (!todo.isEmpty()) {
  55. int x = todo.pop();
  56. if (neigh.get(x).get(1) != 0)
  57. continue;
  58. neigh.get(x).set(1, 1);
  59. if (neigh.get(x).get(0) == 1)
  60. leafesCount++;
  61. if (neigh.get(x).get(0) > 0) {
  62. for (int j = 0; j < neigh.get(x).get(0); j++) {
  63. if (neigh.get(neigh.get(x).get(2 + j)).get(1) == 0)
  64. todo.push(neigh.get(x).get(2 + j));
  65.  
  66. }
  67. }
  68. }
  69.  
  70. if (leafesCount > 3) {
  71. isYes = true;
  72. break;
  73. }
  74.  
  75. }
  76. }
  77.  
  78. if (isYes)
  79. System.out.println("YES");
  80. else
  81. System.out.println("NO");
  82.  
  83.  
  84. /*
  85.   neigh.get(i).set(1, ((Integer)neigh[i].get(1))+1);
  86.   if(((Integer)neigh[i].get(0)) == 1){
  87.   leafesCount ++;
  88.   }
  89.   for (int j = 2; j < neigh[i].size(); j++) {//prvni dva prvky em nezajmaji
  90.   if((Integer)(neigh[(Integer)(neigh[i].get(j))].get(1))==0){
  91.   todo.push((Integer)neigh[i].get(j));
  92.   }
  93.   }
  94.   Integer next = null;
  95.   while(!todo.isEmpty()){
  96.  
  97.   next = todo.pop();
  98.   if(((Integer)neigh[next].get(1)) == 1){
  99.   leafesCount ++;
  100.   System.out.println("add");
  101.   if (leafesCount == 4) {
  102.   break;
  103.   }
  104.   for (int j = 2; j < neigh[i].size(); j++) {//prvni dva prvky em nezajmaji
  105.   todo.push((Integer)neigh[i].get(j));
  106.   }
  107.   }
  108.   if (leafesCount == 4) {
  109.   System.out.println("YES");
  110.   isYes = true;
  111.   break;
  112.   }
  113.   }
  114.   }
  115.   if(isYes != true){
  116.   System.out.println("NO");
  117.   }
  118.  
  119. }*/
  120. }
  121. } catch (Exception e) {
  122. // lol
  123. }
  124. }
  125.  
  126. static String nextToken() throws Exception {
  127. while (!st.hasMoreTokens())
  128. st = new StringTokenizer(input.readLine());
  129. return st.nextToken();
  130. }
  131.  
  132. }
  133.