import java.util.*; public class mis { static List<Integer>[] roadsFromCities; static int connectivityFactor; public static void main(String[] args) throws Exception{ Scanner s = new Scanner(System.in); int cityCount = s.nextInt(); int roadCount = s.nextInt(); connectivityFactor = s.nextInt(); roadsFromCities = new List[cityCount]; for (int i = 0; i < roadCount; i++) { int c1 = s.nextInt() - 1; int c2 = s.nextInt() - 1; addRoad(c1, c2); addRoad(c2, c1); } for (int i = 0; i < cityCount; i++) { List<Integer> roadsFromC1 = roadsFromCities[i]; if (roadsFromC1 != null && roadsFromC1.size() < connectivityFactor) { removeCity(i); } } ArrayList<Integer> biggestComponent = new ArrayList<>(0); int remaining = cityCount; for (int i = 0; i < cityCount; i++) { if (roadsFromCities[i] == null) { continue; } ArrayList<Integer> component = new ArrayList<>(remaining); component(i, component); if (component.size() > biggestComponent.size()) { component.trimToSize(); biggestComponent = component; } remaining -= component.size(); if (biggestComponent.size() >= remaining) { break; } } if (!biggestComponent.isEmpty()) { Collections.sort(biggestComponent); System.out.println(biggestComponent.size()); StringJoiner sj = new StringJoiner(" "); for (int i : biggestComponent) { sj.add(Integer.toString(i + 1)); } System.out.println(sj); } else { System.out.println("NIE"); } } static void addRoad(int c1, int c2) { List<Integer> roadsFromC1 = roadsFromCities[c1]; if (roadsFromC1 == null) { roadsFromC1 = new ArrayList<>(5); roadsFromCities[c1] = roadsFromC1; } roadsFromC1.add(c2); } static void component(int startingCity, List<Integer> component) { Queue<Integer> queue = new LinkedList<>(); component.add(startingCity); queue.addAll(roadsFromCities[startingCity]); roadsFromCities[startingCity] = null; while (!queue.isEmpty()) { int current = queue.remove(); if (roadsFromCities[current] != null) { component.add(current); queue.addAll(roadsFromCities[current]); roadsFromCities[current] = null; } } } static void removeCity(int city) { Queue<Integer> queue = new LinkedList<>(); queue.add(city); while(!queue.isEmpty()) { int current = queue.remove(); List<Integer> neighbors = roadsFromCities[current]; if (neighbors == null) continue; roadsFromCities[current] = null; for (int neighbor: neighbors) { roadsFromCities[neighbor].remove((Object) current); if (neighbor < city && roadsFromCities[neighbor].size() < connectivityFactor) { queue.add(neighbor); } } } } }
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 | import java.util.*; public class mis { static List<Integer>[] roadsFromCities; static int connectivityFactor; public static void main(String[] args) throws Exception{ Scanner s = new Scanner(System.in); int cityCount = s.nextInt(); int roadCount = s.nextInt(); connectivityFactor = s.nextInt(); roadsFromCities = new List[cityCount]; for (int i = 0; i < roadCount; i++) { int c1 = s.nextInt() - 1; int c2 = s.nextInt() - 1; addRoad(c1, c2); addRoad(c2, c1); } for (int i = 0; i < cityCount; i++) { List<Integer> roadsFromC1 = roadsFromCities[i]; if (roadsFromC1 != null && roadsFromC1.size() < connectivityFactor) { removeCity(i); } } ArrayList<Integer> biggestComponent = new ArrayList<>(0); int remaining = cityCount; for (int i = 0; i < cityCount; i++) { if (roadsFromCities[i] == null) { continue; } ArrayList<Integer> component = new ArrayList<>(remaining); component(i, component); if (component.size() > biggestComponent.size()) { component.trimToSize(); biggestComponent = component; } remaining -= component.size(); if (biggestComponent.size() >= remaining) { break; } } if (!biggestComponent.isEmpty()) { Collections.sort(biggestComponent); System.out.println(biggestComponent.size()); StringJoiner sj = new StringJoiner(" "); for (int i : biggestComponent) { sj.add(Integer.toString(i + 1)); } System.out.println(sj); } else { System.out.println("NIE"); } } static void addRoad(int c1, int c2) { List<Integer> roadsFromC1 = roadsFromCities[c1]; if (roadsFromC1 == null) { roadsFromC1 = new ArrayList<>(5); roadsFromCities[c1] = roadsFromC1; } roadsFromC1.add(c2); } static void component(int startingCity, List<Integer> component) { Queue<Integer> queue = new LinkedList<>(); component.add(startingCity); queue.addAll(roadsFromCities[startingCity]); roadsFromCities[startingCity] = null; while (!queue.isEmpty()) { int current = queue.remove(); if (roadsFromCities[current] != null) { component.add(current); queue.addAll(roadsFromCities[current]); roadsFromCities[current] = null; } } } static void removeCity(int city) { Queue<Integer> queue = new LinkedList<>(); queue.add(city); while(!queue.isEmpty()) { int current = queue.remove(); List<Integer> neighbors = roadsFromCities[current]; if (neighbors == null) continue; roadsFromCities[current] = null; for (int neighbor: neighbors) { roadsFromCities[neighbor].remove((Object) current); if (neighbor < city && roadsFromCities[neighbor].size() < connectivityFactor) { queue.add(neighbor); } } } } } |