import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; import java.util.TreeSet; public class kon { static class Sasiedzi { private ArrayList<Integer> sasiedzi = new ArrayList<>(); } static class Droga { ArrayList<Integer> droga; int[] nrWDrodze; int pierwszy; public Droga(int rozmiar, int pierwszy) { droga = new ArrayList<Integer>(); droga.add(pierwszy); nrWDrodze = new int[rozmiar]; nrWDrodze[pierwszy - 1] = 1; this.pierwszy = pierwszy; } public Droga(Droga droga_, int ostatni) { this.pierwszy = droga_.pierwszy; this.droga = new ArrayList<Integer>(droga_.droga); this.droga.add(ostatni); this.nrWDrodze = droga_.nrWDrodze.clone(); this.nrWDrodze[ostatni - 1] = this.droga.size(); } } static class ListaDrog { private ArrayList<Droga> listaDrog = new ArrayList<>(); } public static void main(String[] args) { int liczbaSkrzyzowan = 0, liczbaDrog = 0, liczbaDobrychDrog = 0; Sasiedzi[] graf; TreeSet<Integer> skrzyzowaniaDoSprawdzenia = new TreeSet<>(), skrzyzowaniaDoWypisania = new TreeSet<>(); Scanner skaner = new Scanner(System.in); ListaDrog[] drogi; int[] doIluDrogNalezySkrzyzowanie; boolean[] skrzyzowaniaZ, skrzyzowaniaDo; LinkedList<Integer> skrzyzowaniaDoPrzeszukania = new LinkedList<>(); if(skaner.hasNextInt()) liczbaSkrzyzowan = skaner.nextInt(); if(skaner.hasNextInt()) liczbaDrog = skaner.nextInt(); graf = new Sasiedzi[liczbaSkrzyzowan]; doIluDrogNalezySkrzyzowanie = new int[liczbaSkrzyzowan]; drogi = new ListaDrog[liczbaSkrzyzowan]; skrzyzowaniaZ = new boolean[liczbaSkrzyzowan]; skrzyzowaniaDo = new boolean[liczbaSkrzyzowan]; for(int i = 0; i < liczbaDrog; i++) { int pomZ = 0, pomDo = 0; if(skaner.hasNextInt()) pomZ = skaner.nextInt(); if(skaner.hasNextInt()) pomDo = skaner.nextInt(); skrzyzowaniaZ[pomZ - 1] = true; if(skrzyzowaniaDo[pomZ - 1] == true) skrzyzowaniaDoSprawdzenia.add(pomZ); skrzyzowaniaDo[pomDo - 1] = true; if(skrzyzowaniaZ[pomDo - 1] == true) skrzyzowaniaDoSprawdzenia.add(pomDo); if(graf[pomZ - 1] == null) graf[pomZ - 1] = new Sasiedzi(); graf[pomZ - 1].sasiedzi.add(pomDo); } skaner.close(); while(!skrzyzowaniaDoSprawdzenia.isEmpty()) { int poprz = skrzyzowaniaDoSprawdzenia.pollFirst(); skrzyzowaniaDoPrzeszukania.add(poprz); drogi[poprz - 1] = new ListaDrog(); drogi[poprz - 1].listaDrog.add(new Droga(liczbaSkrzyzowan, poprz)); while(!skrzyzowaniaDoPrzeszukania.isEmpty()) { int akt = skrzyzowaniaDoPrzeszukania.removeFirst(); if(graf[akt - 1] != null) { if(drogi[akt - 1] != null) { for(int sasiad : graf[akt - 1].sasiedzi) { skrzyzowaniaDoSprawdzenia.remove(sasiad); for(Droga droga : drogi[akt - 1].listaDrog) { if(droga.pierwszy == sasiad) { liczbaDobrychDrog += droga.droga.size(); for(int i : droga.droga) doIluDrogNalezySkrzyzowanie[i - 1] += droga.droga.size(); } else if(droga.nrWDrodze[sasiad - 1] > 0) { int j = droga.nrWDrodze[sasiad - 1]; int pom = droga.droga.size() - j + 1; liczbaDobrychDrog += pom; for(int i = j - 1; i < droga.droga.size(); i++) doIluDrogNalezySkrzyzowanie[droga.droga.get(i) - 1] += pom; } else { if(drogi[sasiad - 1] == null) drogi[sasiad - 1] = new ListaDrog(); drogi[sasiad - 1].listaDrog.add(new Droga(droga, sasiad)); skrzyzowaniaDoPrzeszukania.addLast(sasiad); } } } drogi[akt - 1] = null; } } } } if(liczbaDobrychDrog == 0) { System.out.println("NIE"); } else { for(int i = 0; i < liczbaSkrzyzowan; i++) { if(doIluDrogNalezySkrzyzowanie[i] >= liczbaDobrychDrog) { skrzyzowaniaDoWypisania.add(i + 1); } } System.out.println(skrzyzowaniaDoWypisania.size()); if(!skrzyzowaniaDoWypisania.isEmpty()) { int pierwszy = skrzyzowaniaDoWypisania.pollFirst(); System.out.print(pierwszy); for(int d : skrzyzowaniaDoWypisania) { System.out.print(" " + d); } } System.out.println(); } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; import java.util.TreeSet; public class kon { static class Sasiedzi { private ArrayList<Integer> sasiedzi = new ArrayList<>(); } static class Droga { ArrayList<Integer> droga; int[] nrWDrodze; int pierwszy; public Droga(int rozmiar, int pierwszy) { droga = new ArrayList<Integer>(); droga.add(pierwszy); nrWDrodze = new int[rozmiar]; nrWDrodze[pierwszy - 1] = 1; this.pierwszy = pierwszy; } public Droga(Droga droga_, int ostatni) { this.pierwszy = droga_.pierwszy; this.droga = new ArrayList<Integer>(droga_.droga); this.droga.add(ostatni); this.nrWDrodze = droga_.nrWDrodze.clone(); this.nrWDrodze[ostatni - 1] = this.droga.size(); } } static class ListaDrog { private ArrayList<Droga> listaDrog = new ArrayList<>(); } public static void main(String[] args) { int liczbaSkrzyzowan = 0, liczbaDrog = 0, liczbaDobrychDrog = 0; Sasiedzi[] graf; TreeSet<Integer> skrzyzowaniaDoSprawdzenia = new TreeSet<>(), skrzyzowaniaDoWypisania = new TreeSet<>(); Scanner skaner = new Scanner(System.in); ListaDrog[] drogi; int[] doIluDrogNalezySkrzyzowanie; boolean[] skrzyzowaniaZ, skrzyzowaniaDo; LinkedList<Integer> skrzyzowaniaDoPrzeszukania = new LinkedList<>(); if(skaner.hasNextInt()) liczbaSkrzyzowan = skaner.nextInt(); if(skaner.hasNextInt()) liczbaDrog = skaner.nextInt(); graf = new Sasiedzi[liczbaSkrzyzowan]; doIluDrogNalezySkrzyzowanie = new int[liczbaSkrzyzowan]; drogi = new ListaDrog[liczbaSkrzyzowan]; skrzyzowaniaZ = new boolean[liczbaSkrzyzowan]; skrzyzowaniaDo = new boolean[liczbaSkrzyzowan]; for(int i = 0; i < liczbaDrog; i++) { int pomZ = 0, pomDo = 0; if(skaner.hasNextInt()) pomZ = skaner.nextInt(); if(skaner.hasNextInt()) pomDo = skaner.nextInt(); skrzyzowaniaZ[pomZ - 1] = true; if(skrzyzowaniaDo[pomZ - 1] == true) skrzyzowaniaDoSprawdzenia.add(pomZ); skrzyzowaniaDo[pomDo - 1] = true; if(skrzyzowaniaZ[pomDo - 1] == true) skrzyzowaniaDoSprawdzenia.add(pomDo); if(graf[pomZ - 1] == null) graf[pomZ - 1] = new Sasiedzi(); graf[pomZ - 1].sasiedzi.add(pomDo); } skaner.close(); while(!skrzyzowaniaDoSprawdzenia.isEmpty()) { int poprz = skrzyzowaniaDoSprawdzenia.pollFirst(); skrzyzowaniaDoPrzeszukania.add(poprz); drogi[poprz - 1] = new ListaDrog(); drogi[poprz - 1].listaDrog.add(new Droga(liczbaSkrzyzowan, poprz)); while(!skrzyzowaniaDoPrzeszukania.isEmpty()) { int akt = skrzyzowaniaDoPrzeszukania.removeFirst(); if(graf[akt - 1] != null) { if(drogi[akt - 1] != null) { for(int sasiad : graf[akt - 1].sasiedzi) { skrzyzowaniaDoSprawdzenia.remove(sasiad); for(Droga droga : drogi[akt - 1].listaDrog) { if(droga.pierwszy == sasiad) { liczbaDobrychDrog += droga.droga.size(); for(int i : droga.droga) doIluDrogNalezySkrzyzowanie[i - 1] += droga.droga.size(); } else if(droga.nrWDrodze[sasiad - 1] > 0) { int j = droga.nrWDrodze[sasiad - 1]; int pom = droga.droga.size() - j + 1; liczbaDobrychDrog += pom; for(int i = j - 1; i < droga.droga.size(); i++) doIluDrogNalezySkrzyzowanie[droga.droga.get(i) - 1] += pom; } else { if(drogi[sasiad - 1] == null) drogi[sasiad - 1] = new ListaDrog(); drogi[sasiad - 1].listaDrog.add(new Droga(droga, sasiad)); skrzyzowaniaDoPrzeszukania.addLast(sasiad); } } } drogi[akt - 1] = null; } } } } if(liczbaDobrychDrog == 0) { System.out.println("NIE"); } else { for(int i = 0; i < liczbaSkrzyzowan; i++) { if(doIluDrogNalezySkrzyzowanie[i] >= liczbaDobrychDrog) { skrzyzowaniaDoWypisania.add(i + 1); } } System.out.println(skrzyzowaniaDoWypisania.size()); if(!skrzyzowaniaDoWypisania.isEmpty()) { int pierwszy = skrzyzowaniaDoWypisania.pollFirst(); System.out.print(pierwszy); for(int d : skrzyzowaniaDoWypisania) { System.out.print(" " + d); } } System.out.println(); } } } |