import java.io.*; import java.util.*; /** * Created by gmatuszewski on 30.09.2015. */ public class mis { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); mis(br, bw); bw.flush(); bw.close(); System.exit(0); } static boolean[] visited; static Map<Integer, List<Integer>> connections; public static void mis(BufferedReader br, BufferedWriter bw) throws IOException { StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); visited = new boolean[n]; connections = new HashMap<>(); for (int i = 0; i < n; i++) { connections.put(i, new ArrayList<>()); } while (m-- > 0) { st = new StringTokenizer(br.readLine()); int c1 = Integer.parseInt(st.nextToken()) - 1; int c2 = Integer.parseInt(st.nextToken()) - 1; connections.get(c1).add(c2); connections.get(c2).add(c1); } // remove small cities; TreeSet<Integer> testRemoval = new TreeSet<>(connections.keySet()); while(!testRemoval.isEmpty()) { int city = testRemoval.pollFirst(); if (connections.get(city).size() < d) { visited[city] = true; for(Integer c : connections.get(city)){ connections.get(c).remove(Integer.valueOf(city)); testRemoval.add(c); } connections.get(city).clear(); } } List<Integer> cities = Collections.emptyList(); for (int i = 0; i < n; i++) { if (visited[i]) continue; List<Integer> set = compute(i); if (set.size() > cities.size()) cities = set; } Collections.sort(cities); if (cities.size() == 0) bw.write("NIE"); else { bw.write(Integer.toString(cities.size())); bw.newLine(); for (Integer city : cities) { bw.write(Integer.toString(city + 1)); bw.write(" "); } bw.newLine(); } } private static List<Integer> compute(int startCity) { List<Integer> cities = new ArrayList<>(); TreeSet<Integer> toVisit = new TreeSet<>(); toVisit.add(startCity); while (!toVisit.isEmpty()) { int city = toVisit.pollFirst(); if (visited[city]) continue; cities.add(city); visited[city] = true; toVisit.addAll(connections.get(city)); } return cities; } }
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 | import java.io.*; import java.util.*; /** * Created by gmatuszewski on 30.09.2015. */ public class mis { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); mis(br, bw); bw.flush(); bw.close(); System.exit(0); } static boolean[] visited; static Map<Integer, List<Integer>> connections; public static void mis(BufferedReader br, BufferedWriter bw) throws IOException { StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); visited = new boolean[n]; connections = new HashMap<>(); for (int i = 0; i < n; i++) { connections.put(i, new ArrayList<>()); } while (m-- > 0) { st = new StringTokenizer(br.readLine()); int c1 = Integer.parseInt(st.nextToken()) - 1; int c2 = Integer.parseInt(st.nextToken()) - 1; connections.get(c1).add(c2); connections.get(c2).add(c1); } // remove small cities; TreeSet<Integer> testRemoval = new TreeSet<>(connections.keySet()); while(!testRemoval.isEmpty()) { int city = testRemoval.pollFirst(); if (connections.get(city).size() < d) { visited[city] = true; for(Integer c : connections.get(city)){ connections.get(c).remove(Integer.valueOf(city)); testRemoval.add(c); } connections.get(city).clear(); } } List<Integer> cities = Collections.emptyList(); for (int i = 0; i < n; i++) { if (visited[i]) continue; List<Integer> set = compute(i); if (set.size() > cities.size()) cities = set; } Collections.sort(cities); if (cities.size() == 0) bw.write("NIE"); else { bw.write(Integer.toString(cities.size())); bw.newLine(); for (Integer city : cities) { bw.write(Integer.toString(city + 1)); bw.write(" "); } bw.newLine(); } } private static List<Integer> compute(int startCity) { List<Integer> cities = new ArrayList<>(); TreeSet<Integer> toVisit = new TreeSet<>(); toVisit.add(startCity); while (!toVisit.isEmpty()) { int city = toVisit.pollFirst(); if (visited[city]) continue; cities.add(city); visited[city] = true; toVisit.addAll(connections.get(city)); } return cities; } } |