import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class mis { static int n; static int m; static int d; static HashSet<Integer> connected[]; static HashSet<Integer> selectedSet; static HashSet<Integer> removedSet; static void readInput() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer fl = new StringTokenizer(br.readLine()); n = Integer.parseInt(fl.nextToken()); m = Integer.parseInt(fl.nextToken()); d = Integer.parseInt(fl.nextToken()); connected = new HashSet[n]; for (int i = 0; i < n; i++) connected[i] = new HashSet<>(); for (int i = 0; i < m; i++) { StringTokenizer nl = new StringTokenizer(br.readLine()); int a = Integer.parseInt(nl.nextToken()) - 1; int b = Integer.parseInt(nl.nextToken()) - 1; connected[a].add(b); connected[b].add(a); } } static class SelectedAndRemoved { HashSet<Integer> selected; HashSet<Integer> removed; SelectedAndRemoved(HashSet<Integer> selected, HashSet<Integer> removed) { this.selected = selected; this.removed = removed; } } static SelectedAndRemoved sweep() { HashSet<Integer> newSelected = new HashSet<>(); HashSet<Integer> newRemoved = new HashSet<>(); for (Integer i : selectedSet) { if (connected[i].size() >= d) { newSelected.add(i); } else { newRemoved.add(i); } } return new SelectedAndRemoved(newSelected, newRemoved); } static void printOutput(Set<Integer> maximalSet) { if (maximalSet.isEmpty()) { System.out.println("NIE"); } else { System.out.println(maximalSet.size()); Integer[] maximalList = maximalSet.toArray(new Integer[maximalSet.size()]); Arrays.sort(maximalList); StringJoiner sj = new StringJoiner(" "); for (int i : maximalList) sj.add(Integer.toString(i+1)); System.out.println(sj.toString()); } } static Set<Integer> findConnected() { Iterator<Integer> it = selectedSet.iterator(); if (it.hasNext()) { Set<Integer> conComp = new HashSet<>(); Queue<Integer> que = new LinkedList<>(); Integer v = it.next(); conComp.add(v); que.add(v); while (!que.isEmpty()) { v = que.remove(); for (Integer con : connected[v]) { if (conComp.add(con)) { que.add(con); } } } return conComp; } else return Collections.emptySet(); } public static void main(String[] args) throws IOException { readInput(); selectedSet = new HashSet<>(); removedSet = new HashSet<>(); for (int i = 0; i < n; i++) selectedSet.add(i); for (SelectedAndRemoved sar = sweep(); !sar.removed.isEmpty(); sar = sweep()) { selectedSet = sar.selected; for (int i : selectedSet) { connected[i].removeAll(sar.removed); } } Set<Integer> maximalSet = Collections.emptySet(); while (selectedSet.size() > maximalSet.size()) { Set<Integer> conComp = findConnected(); if (conComp.size() > maximalSet.size()) maximalSet = conComp; selectedSet.removeAll(conComp); } printOutput(maximalSet); } }
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 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class mis { static int n; static int m; static int d; static HashSet<Integer> connected[]; static HashSet<Integer> selectedSet; static HashSet<Integer> removedSet; static void readInput() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer fl = new StringTokenizer(br.readLine()); n = Integer.parseInt(fl.nextToken()); m = Integer.parseInt(fl.nextToken()); d = Integer.parseInt(fl.nextToken()); connected = new HashSet[n]; for (int i = 0; i < n; i++) connected[i] = new HashSet<>(); for (int i = 0; i < m; i++) { StringTokenizer nl = new StringTokenizer(br.readLine()); int a = Integer.parseInt(nl.nextToken()) - 1; int b = Integer.parseInt(nl.nextToken()) - 1; connected[a].add(b); connected[b].add(a); } } static class SelectedAndRemoved { HashSet<Integer> selected; HashSet<Integer> removed; SelectedAndRemoved(HashSet<Integer> selected, HashSet<Integer> removed) { this.selected = selected; this.removed = removed; } } static SelectedAndRemoved sweep() { HashSet<Integer> newSelected = new HashSet<>(); HashSet<Integer> newRemoved = new HashSet<>(); for (Integer i : selectedSet) { if (connected[i].size() >= d) { newSelected.add(i); } else { newRemoved.add(i); } } return new SelectedAndRemoved(newSelected, newRemoved); } static void printOutput(Set<Integer> maximalSet) { if (maximalSet.isEmpty()) { System.out.println("NIE"); } else { System.out.println(maximalSet.size()); Integer[] maximalList = maximalSet.toArray(new Integer[maximalSet.size()]); Arrays.sort(maximalList); StringJoiner sj = new StringJoiner(" "); for (int i : maximalList) sj.add(Integer.toString(i+1)); System.out.println(sj.toString()); } } static Set<Integer> findConnected() { Iterator<Integer> it = selectedSet.iterator(); if (it.hasNext()) { Set<Integer> conComp = new HashSet<>(); Queue<Integer> que = new LinkedList<>(); Integer v = it.next(); conComp.add(v); que.add(v); while (!que.isEmpty()) { v = que.remove(); for (Integer con : connected[v]) { if (conComp.add(con)) { que.add(con); } } } return conComp; } else return Collections.emptySet(); } public static void main(String[] args) throws IOException { readInput(); selectedSet = new HashSet<>(); removedSet = new HashSet<>(); for (int i = 0; i < n; i++) selectedSet.add(i); for (SelectedAndRemoved sar = sweep(); !sar.removed.isEmpty(); sar = sweep()) { selectedSet = sar.selected; for (int i : selectedSet) { connected[i].removeAll(sar.removed); } } Set<Integer> maximalSet = Collections.emptySet(); while (selectedSet.size() > maximalSet.size()) { Set<Integer> conComp = findConnected(); if (conComp.size() > maximalSet.size()) maximalSet = conComp; selectedSet.removeAll(conComp); } printOutput(maximalSet); } } |