import java.util.*; public class mis { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int d = scanner.nextInt(); List<List<Integer>> roads = new ArrayList<List<Integer>>(n); List<Boolean> removed = new ArrayList<Boolean>(n); List<Integer> degrees = new ArrayList<Integer>(n); List<Boolean> visited = new ArrayList<Boolean>(n); Queue<Integer> toRemove = new LinkedList<Integer>(); for(int i = 0; i < n; i++) { roads.add(new LinkedList<Integer>()); removed.add(false); degrees.add(0); visited.add(false); } for(int i = 0; i < m; i++) { int a1 = scanner.nextInt() - 1; int a2 = scanner.nextInt() - 1; roads.get(a1).add(a2); roads.get(a2).add(a1); degrees.set(a1, degrees.get(a1) + 1); degrees.set(a2, degrees.get(a2) + 1); } for(int i = 0; i < n; i++) { if(degrees.get(i) < d) { removed.set(i, true); toRemove.add(i); } } while(toRemove.peek() != null) { int currentlyRemoved = toRemove.poll(); List<Integer> currentRoads = roads.get(currentlyRemoved); for(Integer target: currentRoads) { int targetDegree = degrees.get(target); if(targetDegree - 1 < d && !removed.get(target)) { removed.set(target, true); toRemove.add(target); } degrees.set(target, targetDegree - 1); } } int max = 0; List<Integer> ids = new ArrayList<Integer>(); for(int i = 0; i < n; i++) { if(!removed.get(i) && !visited.get(i)) { List<Integer> currentIds = new ArrayList<Integer>(); Queue<Integer> bfsQueue = new LinkedList<Integer>(); bfsQueue.add(i); visited.set(i, true); while(bfsQueue.peek() != null) { int current = bfsQueue.poll(); currentIds.add(current); for(Integer target: roads.get(current)) { if(!removed.get(target) && !visited.get(target)) { bfsQueue.add(target); visited.set(target, true); } } } if(max < currentIds.size()) { max = currentIds.size(); ids = currentIds; } } } Collections.sort(ids); if(max > 1) { System.out.println(max); for(Integer id: ids) { System.out.print((id + 1) + " "); } System.out.println(); } else { System.out.println("NIE"); } } }
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 | import java.util.*; public class mis { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int d = scanner.nextInt(); List<List<Integer>> roads = new ArrayList<List<Integer>>(n); List<Boolean> removed = new ArrayList<Boolean>(n); List<Integer> degrees = new ArrayList<Integer>(n); List<Boolean> visited = new ArrayList<Boolean>(n); Queue<Integer> toRemove = new LinkedList<Integer>(); for(int i = 0; i < n; i++) { roads.add(new LinkedList<Integer>()); removed.add(false); degrees.add(0); visited.add(false); } for(int i = 0; i < m; i++) { int a1 = scanner.nextInt() - 1; int a2 = scanner.nextInt() - 1; roads.get(a1).add(a2); roads.get(a2).add(a1); degrees.set(a1, degrees.get(a1) + 1); degrees.set(a2, degrees.get(a2) + 1); } for(int i = 0; i < n; i++) { if(degrees.get(i) < d) { removed.set(i, true); toRemove.add(i); } } while(toRemove.peek() != null) { int currentlyRemoved = toRemove.poll(); List<Integer> currentRoads = roads.get(currentlyRemoved); for(Integer target: currentRoads) { int targetDegree = degrees.get(target); if(targetDegree - 1 < d && !removed.get(target)) { removed.set(target, true); toRemove.add(target); } degrees.set(target, targetDegree - 1); } } int max = 0; List<Integer> ids = new ArrayList<Integer>(); for(int i = 0; i < n; i++) { if(!removed.get(i) && !visited.get(i)) { List<Integer> currentIds = new ArrayList<Integer>(); Queue<Integer> bfsQueue = new LinkedList<Integer>(); bfsQueue.add(i); visited.set(i, true); while(bfsQueue.peek() != null) { int current = bfsQueue.poll(); currentIds.add(current); for(Integer target: roads.get(current)) { if(!removed.get(target) && !visited.get(target)) { bfsQueue.add(target); visited.set(target, true); } } } if(max < currentIds.size()) { max = currentIds.size(); ids = currentIds; } } } Collections.sort(ids); if(max > 1) { System.out.println(max); for(Integer id: ids) { System.out.print((id + 1) + " "); } System.out.println(); } else { System.out.println("NIE"); } } } |