Go to diff to previous submission
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Set; /** * * @author cteam92 */ public class Fn { static ArrayList<LinkedList<Integer>> graph; static int n, m; static boolean[] visited; static int[] components; static void markComponents() { components = new int[n]; // visited = new boolean[n]; // for (int i = 0; i < n; i++) { // dfs(i, i); // } } static void dfs(int node, int leader) { if (visited[node]) { return; } visited[node] = true; components[node] = leader; dfs(neighbour, leader); } } while (true) { int V1, V2; if (!sc.hasNext()) { break; } n = sc.nextInt(); m = sc.nextInt(); sc.nextLine(); graph = new ArrayList<LinkedList<Integer>>(); for (int i = 0; i < n; i++) { graph.add(new LinkedList<Integer>()); } for (int i = 0; i < m; i++) { V1 = sc.nextInt(); V2 = sc.nextInt(); sc.nextLine(); LinkedList<Integer> vertex; vertex = graph.get(V1 - 1); vertex.add(V2 - 1); graph.set(V1 - 1, vertex); vertex = graph.get(V2 - 1); vertex.add(V1 - 1); graph.set(V2 - 1, vertex); } /*System.out.println("----"); for (int i=0; i<n; i++) { System.out.println(graph.get(i).toString()); }*/ //markComponents(); //System.out.println(Arrays.toString(components)); //Set<Integer> withY = new HashSet<Integer>(); Set<Integer> yNodes = new HashSet<Integer>(); boolean bunny = false; for (int node = 0; node < n; node++) { int neighbourCount = graph.get(node).size(); if (neighbourCount >= 4) { bunny = true; break; } else if (neighbourCount == 3) { Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node)); for (int i : yNodes) { Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i)); //System.out.println("nodeYSet pro " + i + " " + nodeYSet.toString()); if (nodeYSet.contains(node)) { //System.out.println("sousedi" + i + " " + node); nodeYSet.retainAll(nodeSet); //System.out.println("po pruniku" + nodeYSet.toString()); if (nodeYSet.isEmpty()) { //System.out.println("1"); bunny = true; break; } } else { //System.out.println("nejsou sousedi" + i + " " + node); nodeYSet.retainAll(nodeSet); //System.out.println("po pruniku" + nodeYSet.toString()); if (nodeYSet.size() <= 1) { //System.out.println("2"); bunny = true; break; } } } if (bunny) break; yNodes.add(node); } } if (bunny) { } else { } } } }
--- c5.s1107.cteam092.fn.java.0.Fn.java +++ c5.s1124.cteam092.fn.java.0.Fn.java @@ -85,12 +85,9 @@ System.out.println(graph.get(i).toString()); }*/ - markComponents(); + //markComponents(); //System.out.println(Arrays.toString(components)); //Set<Integer> withY = new HashSet<Integer>(); - Map<Integer, Set<Integer>> yNodes = new HashMap<Integer, Set<Integer>>(); - for (int i = 0; i < n; i++) { - yNodes.put(i, new HashSet<Integer>()); - } + Set<Integer> yNodes = new HashSet<Integer>(); boolean bunny = false; @@ -105,9 +102,5 @@ 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])) { + for (int i : yNodes) { Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i)); @@ -135,5 +128,5 @@ } if (bunny) break; - yNodes.get(components[node]).add(node); + yNodes.add(node); } }