Go to diff to previous submission
import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.Set; public class Fn { static class Kozel { public ArrayList<Integer> sousedi = new ArrayList<Integer>(); } static Set<Integer> kudylezekozolezec = new HashSet<Integer>(); while (scanner.hasNext()) { int nodes = scanner.nextInt(); int edges = scanner.nextInt(); Kozel[] kozelnik = new Kozel[nodes + 1]; for (int i=1; i<=nodes; i++) { kozelnik[i] = new Kozel(); } for (int i=0; i<edges; i++) { int node1 = scanner.nextInt(); int node2 = scanner.nextInt(); kozelnik[node1].sousedi.add(node2); kozelnik[node2].sousedi.add(node1); } boolean hasBunny = false; for (int i=1; i<=nodes; i++) { if (kozelnik[i].sousedi.size() >= 4) { hasBunny = true; break; } else if (kozelnik[i].sousedi.size() == 3) { hasBunny = prolez(kozelnik, i); if (hasBunny) break; } } if (hasBunny) { } else { } } } public static boolean prolez(Kozel[] kozinec, int index) { kudylezekozolezec.clear(); kudylezekozolezec.add(index); if (kozolezec(kozinec, i)) return true; } return false; } public static boolean kozolezec(Kozel[] kozinec, int index) { while (kozinec[index].sousedi.size() == 2) { kudylezekozolezec.add(index); if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(0))) { index = kozinec[index].sousedi.get(0); } else if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(1))) { index = kozinec[index].sousedi.get(1); } else { return false; } } if (kozinec[index].sousedi.size() > 2) { return true; // to pochopime... } else { return false; } } }
--- c5.s547.cteam038.fn.java.0.Fn.java +++ c5.s699.cteam038.fn.java.0.Fn.java @@ -1,8 +1,18 @@ +import java.util.ArrayList; +import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Scanner; +import java.util.Set; public class Fn { + + static class Kozel { + + public ArrayList<Integer> sousedi = new ArrayList<Integer>(); + } + + static Set<Integer> kudylezekozolezec = new HashSet<Integer>(); public static void main(String [] args) { @@ -12,17 +22,24 @@ int edges = scanner.nextInt(); - int [] poile = new int[nodes + 1]; + Kozel[] kozelnik = new Kozel[nodes + 1]; + for (int i=1; i<=nodes; i++) { + kozelnik[i] = new Kozel(); + } + for (int i=0; i<edges; i++) { int node1 = scanner.nextInt(); int node2 = scanner.nextInt(); - ++poile[node1]; - ++poile[node2]; + kozelnik[node1].sousedi.add(node2); + kozelnik[node2].sousedi.add(node1); } boolean hasBunny = false; - for (int i=0; i<nodes; i++) { - if (poile[i] >= 4) { + for (int i=1; i<=nodes; i++) { + if (kozelnik[i].sousedi.size() >= 4) { hasBunny = true; break; + } else if (kozelnik[i].sousedi.size() == 3) { + hasBunny = prolez(kozelnik, i); + if (hasBunny) break; } } @@ -35,4 +52,39 @@ } } + + public static boolean prolez(Kozel[] kozinec, int index) { + + for (Integer i : kozinec[index].sousedi) { + + kudylezekozolezec.clear(); + kudylezekozolezec.add(index); + if (kozolezec(kozinec, i)) return true; + } + + return false; + } + + public static boolean kozolezec(Kozel[] kozinec, int index) { + + + while (kozinec[index].sousedi.size() == 2) { + + kudylezekozolezec.add(index); + + if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(0))) { + index = kozinec[index].sousedi.get(0); + } else if (!kudylezekozolezec.contains(kozinec[index].sousedi.get(1))) { + index = kozinec[index].sousedi.get(1); + } else { + return false; + } + } + + if (kozinec[index].sousedi.size() > 2) { + return true; // to pochopime... + } else { + return false; + } + }