import java.util.ArrayList; import java.util.Scanner; import java.util.TreeSet; public class mis { static class ListaSasiadow { private ArrayList<Integer> sasiedzi; public ListaSasiadow() { sasiedzi = new ArrayList<Integer>(); } } public static void redukcja(ListaSasiadow[] graf, TreeSet<Integer> zbiorMiastS, TreeSet<Integer> zbiorZlychMiast, int ileMinimalnieSasiadow) { while(!zbiorZlychMiast.isEmpty()) { int m = zbiorZlychMiast.pollFirst(); zbiorMiastS.remove(m); for(int k : graf[m - 1].sasiedzi) { graf[k - 1].sasiedzi.remove((Integer)m); if(graf[k - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(k); } graf[m - 1] = null; } } public static TreeSet<Integer> najwiekszySpojnyPodgraf(ListaSasiadow[] sasiedzi, TreeSet<Integer> zbiorMiastS) { TreeSet<Integer> najwiekszySpojnyPodgraf = null; TreeSet<Integer> odwiedzoneMiasta = new TreeSet<Integer>(); for(int miasto : zbiorMiastS) { TreeSet<Integer> pom = null; if(!odwiedzoneMiasta.contains(miasto)) { pom = stworzDrzewoSasiadow(miasto, sasiedzi, odwiedzoneMiasta); if(najwiekszySpojnyPodgraf == null || pom.size() > najwiekszySpojnyPodgraf.size()) najwiekszySpojnyPodgraf = pom; } } return najwiekszySpojnyPodgraf; } public static TreeSet<Integer> stworzDrzewoSasiadow(int miasto, ListaSasiadow[] sasiedzi, TreeSet<Integer> odwiedzoneMiasta) { TreeSet<Integer> pom = new TreeSet<>(); TreeSet<Integer> drzewoSasiadow = new TreeSet<>(); pom.add(miasto); drzewoSasiadow.add(miasto); odwiedzoneMiasta.add(miasto); for(int k : sasiedzi[miasto - 1].sasiedzi) { pom.add(k); drzewoSasiadow.add(k); odwiedzoneMiasta.add(k); } while(!pom.isEmpty()) { int k = pom.pollFirst(); for(int l : sasiedzi[k - 1].sasiedzi) { if(!drzewoSasiadow.contains(l)) { pom.add(l); drzewoSasiadow.add(l); odwiedzoneMiasta.add(l); } } } return drzewoSasiadow; } public static void main(String[] args) { Scanner skaner = new Scanner(System.in); ListaSasiadow[] graf; int liczbaMiast = 0, liczbaDrog = 0, ileMinimalnieSasiadow = 0; TreeSet<Integer> zbiorMiastS = new TreeSet<Integer>(), zbiorZlychMiast = new TreeSet<Integer>(); if(skaner.hasNextInt()) liczbaMiast = skaner.nextInt(); graf = new ListaSasiadow[liczbaMiast]; if(skaner.hasNextInt()) liczbaDrog = skaner.nextInt(); if(skaner.hasNextInt()) ileMinimalnieSasiadow = skaner.nextInt(); int pocz = 0, kon = 0; for(int i = 0; i < liczbaDrog; i++) { if(skaner.hasNextInt()) pocz = skaner.nextInt(); if(skaner.hasNextInt()) kon = skaner.nextInt(); zbiorMiastS.add(pocz); zbiorMiastS.add(kon); if(graf[pocz - 1] == null) graf[pocz - 1] = new ListaSasiadow(); graf[pocz - 1].sasiedzi.add(kon); if(graf[pocz - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(pocz); else zbiorZlychMiast.remove(pocz); if(graf[kon - 1] == null) graf[kon - 1] = new ListaSasiadow(); graf[kon - 1].sasiedzi.add(pocz); if(graf[kon - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(kon); else zbiorZlychMiast.remove(kon); } skaner.close(); redukcja(graf, zbiorMiastS, zbiorZlychMiast, ileMinimalnieSasiadow); if(zbiorMiastS.isEmpty()) System.out.println("NIE"); else { TreeSet<Integer> najwiekszySpojnyPodgraf = najwiekszySpojnyPodgraf(graf, zbiorMiastS); System.out.println(najwiekszySpojnyPodgraf.size()); System.out.print(najwiekszySpojnyPodgraf.pollFirst()); for(int m : najwiekszySpojnyPodgraf) { System.out.print(" " + m); } } } }
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 | import java.util.ArrayList; import java.util.Scanner; import java.util.TreeSet; public class mis { static class ListaSasiadow { private ArrayList<Integer> sasiedzi; public ListaSasiadow() { sasiedzi = new ArrayList<Integer>(); } } public static void redukcja(ListaSasiadow[] graf, TreeSet<Integer> zbiorMiastS, TreeSet<Integer> zbiorZlychMiast, int ileMinimalnieSasiadow) { while(!zbiorZlychMiast.isEmpty()) { int m = zbiorZlychMiast.pollFirst(); zbiorMiastS.remove(m); for(int k : graf[m - 1].sasiedzi) { graf[k - 1].sasiedzi.remove((Integer)m); if(graf[k - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(k); } graf[m - 1] = null; } } public static TreeSet<Integer> najwiekszySpojnyPodgraf(ListaSasiadow[] sasiedzi, TreeSet<Integer> zbiorMiastS) { TreeSet<Integer> najwiekszySpojnyPodgraf = null; TreeSet<Integer> odwiedzoneMiasta = new TreeSet<Integer>(); for(int miasto : zbiorMiastS) { TreeSet<Integer> pom = null; if(!odwiedzoneMiasta.contains(miasto)) { pom = stworzDrzewoSasiadow(miasto, sasiedzi, odwiedzoneMiasta); if(najwiekszySpojnyPodgraf == null || pom.size() > najwiekszySpojnyPodgraf.size()) najwiekszySpojnyPodgraf = pom; } } return najwiekszySpojnyPodgraf; } public static TreeSet<Integer> stworzDrzewoSasiadow(int miasto, ListaSasiadow[] sasiedzi, TreeSet<Integer> odwiedzoneMiasta) { TreeSet<Integer> pom = new TreeSet<>(); TreeSet<Integer> drzewoSasiadow = new TreeSet<>(); pom.add(miasto); drzewoSasiadow.add(miasto); odwiedzoneMiasta.add(miasto); for(int k : sasiedzi[miasto - 1].sasiedzi) { pom.add(k); drzewoSasiadow.add(k); odwiedzoneMiasta.add(k); } while(!pom.isEmpty()) { int k = pom.pollFirst(); for(int l : sasiedzi[k - 1].sasiedzi) { if(!drzewoSasiadow.contains(l)) { pom.add(l); drzewoSasiadow.add(l); odwiedzoneMiasta.add(l); } } } return drzewoSasiadow; } public static void main(String[] args) { Scanner skaner = new Scanner(System.in); ListaSasiadow[] graf; int liczbaMiast = 0, liczbaDrog = 0, ileMinimalnieSasiadow = 0; TreeSet<Integer> zbiorMiastS = new TreeSet<Integer>(), zbiorZlychMiast = new TreeSet<Integer>(); if(skaner.hasNextInt()) liczbaMiast = skaner.nextInt(); graf = new ListaSasiadow[liczbaMiast]; if(skaner.hasNextInt()) liczbaDrog = skaner.nextInt(); if(skaner.hasNextInt()) ileMinimalnieSasiadow = skaner.nextInt(); int pocz = 0, kon = 0; for(int i = 0; i < liczbaDrog; i++) { if(skaner.hasNextInt()) pocz = skaner.nextInt(); if(skaner.hasNextInt()) kon = skaner.nextInt(); zbiorMiastS.add(pocz); zbiorMiastS.add(kon); if(graf[pocz - 1] == null) graf[pocz - 1] = new ListaSasiadow(); graf[pocz - 1].sasiedzi.add(kon); if(graf[pocz - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(pocz); else zbiorZlychMiast.remove(pocz); if(graf[kon - 1] == null) graf[kon - 1] = new ListaSasiadow(); graf[kon - 1].sasiedzi.add(pocz); if(graf[kon - 1].sasiedzi.size() < ileMinimalnieSasiadow) zbiorZlychMiast.add(kon); else zbiorZlychMiast.remove(kon); } skaner.close(); redukcja(graf, zbiorMiastS, zbiorZlychMiast, ileMinimalnieSasiadow); if(zbiorMiastS.isEmpty()) System.out.println("NIE"); else { TreeSet<Integer> najwiekszySpojnyPodgraf = najwiekszySpojnyPodgraf(graf, zbiorMiastS); System.out.println(najwiekszySpojnyPodgraf.size()); System.out.print(najwiekszySpojnyPodgraf.pollFirst()); for(int m : najwiekszySpojnyPodgraf) { System.out.print(" " + m); } } } } |