import java.util.*; import static java.lang.Integer.parseInt; public class mis { static int cityCount; static int roadCount; static int dFactor; static Set<Integer>[] cities; static int[] result; static Queue<Integer> citiesToCheck = new LinkedList<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] firstLine = scanner.nextLine().split(" "); cityCount = parseInt(firstLine[0]); roadCount = parseInt(firstLine[1]); dFactor = parseInt(firstLine[2]); cities = new Set[cityCount + 1]; result = new int[cityCount + 1]; for (int i = 1; i <= cityCount; i++) { cities[i] = new HashSet<>(); result[i] = -1; } for (int i = 0; i < roadCount; i++) { String[] line = scanner.nextLine().split(" "); addRoad(parseInt(line[0]), parseInt(line[1])); } for (int cityA = 1; cityA <= cityCount; cityA++) { removeUselessCities(cityA); } while (!citiesToCheck.isEmpty()) { removeUselessCities(citiesToCheck.poll()); } int indicator = 0; int resultSize = 0; for (int city = 1; city <= cityCount; city++) { Set<Integer> roadsOfCity = cities[city]; if (roadsOfCity != null && result[city] != indicator) { int newIndicator = city; int newResultSize = 0; result[city] = newIndicator; newResultSize++; newResultSize += addRoadsToResult(newIndicator, roadsOfCity); cities[city] = null; if (newResultSize > resultSize) { indicator = newIndicator; resultSize = newResultSize; } } } if (resultSize == 0) { System.out.println("NIE"); return; } System.out.println(resultSize); for (int i = 1; i <= cityCount; i++) { if (result[i] == indicator) { System.out.print(i); System.out.print(" "); } } System.out.println(); } private static void removeUselessCities(int cityA) { if (cities[cityA] == null) return; Set<Integer> roadsOfCityA = cities[cityA]; if (roadsOfCityA.size() < dFactor) { Iterator<Integer> iterator = roadsOfCityA.iterator(); while (iterator.hasNext()) { int cityB = iterator.next(); Set<Integer> roadsOfCityB = cities[cityB]; roadsOfCityB.remove(cityA); iterator.remove(); if (roadsOfCityB.size() < dFactor) { citiesToCheck.add(cityB); } } cities[cityA] = null; } } private static int addRoadsToResult(int indicator, Set<Integer> roadsOfCityA) { int resultSize = 0; for (int cityB : roadsOfCityA) { if (result[cityB] != indicator) { result[cityB] = indicator; resultSize++; resultSize += addRoadsToResult(indicator, cities[cityB]); } } return resultSize; } static void addRoad(int cityA, int cityB) { cities[cityA].add(cityB); cities[cityB].add(cityA); } }
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 | import java.util.*; import static java.lang.Integer.parseInt; public class mis { static int cityCount; static int roadCount; static int dFactor; static Set<Integer>[] cities; static int[] result; static Queue<Integer> citiesToCheck = new LinkedList<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] firstLine = scanner.nextLine().split(" "); cityCount = parseInt(firstLine[0]); roadCount = parseInt(firstLine[1]); dFactor = parseInt(firstLine[2]); cities = new Set[cityCount + 1]; result = new int[cityCount + 1]; for (int i = 1; i <= cityCount; i++) { cities[i] = new HashSet<>(); result[i] = -1; } for (int i = 0; i < roadCount; i++) { String[] line = scanner.nextLine().split(" "); addRoad(parseInt(line[0]), parseInt(line[1])); } for (int cityA = 1; cityA <= cityCount; cityA++) { removeUselessCities(cityA); } while (!citiesToCheck.isEmpty()) { removeUselessCities(citiesToCheck.poll()); } int indicator = 0; int resultSize = 0; for (int city = 1; city <= cityCount; city++) { Set<Integer> roadsOfCity = cities[city]; if (roadsOfCity != null && result[city] != indicator) { int newIndicator = city; int newResultSize = 0; result[city] = newIndicator; newResultSize++; newResultSize += addRoadsToResult(newIndicator, roadsOfCity); cities[city] = null; if (newResultSize > resultSize) { indicator = newIndicator; resultSize = newResultSize; } } } if (resultSize == 0) { System.out.println("NIE"); return; } System.out.println(resultSize); for (int i = 1; i <= cityCount; i++) { if (result[i] == indicator) { System.out.print(i); System.out.print(" "); } } System.out.println(); } private static void removeUselessCities(int cityA) { if (cities[cityA] == null) return; Set<Integer> roadsOfCityA = cities[cityA]; if (roadsOfCityA.size() < dFactor) { Iterator<Integer> iterator = roadsOfCityA.iterator(); while (iterator.hasNext()) { int cityB = iterator.next(); Set<Integer> roadsOfCityB = cities[cityB]; roadsOfCityB.remove(cityA); iterator.remove(); if (roadsOfCityB.size() < dFactor) { citiesToCheck.add(cityB); } } cities[cityA] = null; } } private static int addRoadsToResult(int indicator, Set<Integer> roadsOfCityA) { int resultSize = 0; for (int cityB : roadsOfCityA) { if (result[cityB] != indicator) { result[cityB] = indicator; resultSize++; resultSize += addRoadsToResult(indicator, cities[cityB]); } } return resultSize; } static void addRoad(int cityA, int cityB) { cities[cityA].add(cityB); cities[cityB].add(cityA); } } |