Source code for submission s1004

Go to diff to previous submission

import java.io.*;
import java.util.*;
 
class Main {
  static int N, E;
  static Node[] nodes;
  static ArrayList<Node> checks;
  public static void main(String args[]) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line;
 
    while((line = br.readLine()) != null) {
      int a[] = new int[2];
      parseIntArr(line.toCharArray(), a);
      N = a[0]; E = a[1];
      nodes = new Node[N+1];
      ArrayList<Node> d3 = new ArrayList<Node>();
      for(int i = 1; i <= N; i++) nodes[i] = new Node();
 
      boolean found = false;
 
      for(int i = 0; i < E; i++) {
	if(!found) parseIntArr(br.readLine().toCharArray(), a);
	else {
	  br.readLine();
	  continue;
	}
 
	nodes[a[0]].edges.add(a[1]);
	nodes[a[1]].edges.add(a[0]);
 
	if(nodes[a[0]].edges.size() == 4) found = true;
	else if(nodes[a[1]].edges.size() == 4) found = true;
	else if(nodes[a[0]].edges.size() == 3) d3.add(nodes[a[0]]);
	else if(nodes[a[1]].edges.size() == 3) d3.add(nodes[a[1]]);
      }
 
      if(found) System.out.println("YES");
      else {
	outer:
	for(Node n : d3) {
	  checks = new ArrayList<Node>();
	  walk(n);
	  for(int i = 0; i < checks.size(); i++) {
	    for(int j = i+1; j < checks.size(); j++) {
	      if(check(checks.get(i), checks.get(j))) {
		found = true;
		break outer;
	      }
	    }
	  }
	}
	if(found) System.out.println("YES");
	else System.out.println("NO");
      }
    }
  }
 
  static void walk(Node n) {
    if(n.visited) return;
    else {
      n.visited = true;
      if(n.edges.size() >= 3) {
	checks.add(n);
      }
      for(Integer i : n.edges) walk(nodes[i]);
    }
  }
 
  static boolean check(Node n1, Node n2) {
    HashSet<Integer> hs = new HashSet<Integer>(4);
    hs.addAll(n1.edges);
    for(Integer i : n2.edges) {
      if(hs.contains(i)) return false;
    }
    return true;
  }
 
  public static void parseIntArr(char[] arr, int[] target)
    {
        int i = 0;
        int acc = -1;
 
        for(char ch :arr)
        {
            if(ch == ' ')
            {
                if(acc!= -1)
                {
                    target[i++] = acc;
                    acc = -1;
                }
            }
            else if(acc == -1)
                acc = ch - '0';
            else
                acc = acc * 10 + (ch - '0');
        }
        if(acc != -1)
            target[i] = acc;
    }
}
 
class Node {
  boolean visited = false;
  ArrayList<Integer> edges = new ArrayList<Integer>(4);
}

Diff to submission s839

--- c5.s839.cteam028.fn.java.0.Main.java
+++ c5.s1004.cteam028.fn.java.0.Main.java
@@ -5,4 +5,5 @@
   static int N, E;
   static Node[] nodes;
+  static ArrayList<Node> checks;
   public static void main(String args[]) throws Exception {
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
@@ -37,8 +38,15 @@
       if(found) System.out.println("YES");
       else {
+        outer:
         for(Node n : d3) {
-          if(walk(n, false)) {
-            found = true;
-            break;
+          checks = new ArrayList<Node>();
+          walk(n);
+          for(int i = 0; i < checks.size(); i++) {
+            for(int j = i+1; j < checks.size(); j++) {
+              if(check(checks.get(i), checks.get(j))) {
+                found = true;
+                break outer;
+              }
+            }
           }
         }
@@ -49,19 +57,22 @@
   }
 
-  static boolean walk(Node n, boolean foundFirst) {
-    if(n.visited) return false;
+  static void walk(Node n) {
+    if(n.visited) return;
     else {
       n.visited = true;
-      if(n.edges.size() == 3) {
-        if(foundFirst) return true;
-        else foundFirst = true;
+      if(n.edges.size() >= 3) {
+        checks.add(n);
       }
+      for(Integer i : n.edges) walk(nodes[i]);
+    }
+  }
 
-      for(Integer i : n.edges) {
-        boolean result = walk(nodes[i], foundFirst);
-        if(result) return true;
-      }
+  static boolean check(Node n1, Node n2) {
+    HashSet<Integer> hs = new HashSet<Integer>(4);
+    hs.addAll(n1.edges);
+    for(Integer i : n2.edges) {
+      if(hs.contains(i)) return false;
     }
-    return false;
+    return true;
   }