import java.util.*; public class mis { private int numberOfCities; private int minNumberOfPathsFromCity; private int[][] cityConnections; private Set<Integer> visitedVertex = new HashSet<>(); private List<Integer> longestPath = new ArrayList<>(); private Map<Integer, Integer> cityWithNumberOfPaths = new HashMap<>(); public static void main(String[] args) { mis mistrzostwa = new mis(); mistrzostwa.readValuesFromCommandLine(); mistrzostwa.findCities(); System.exit(0); } private void findCities() { Iterator<Map.Entry<Integer, Integer>> it = cityWithNumberOfPaths.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); int vertex = entry.getKey(); List<Integer> tempLongestPath = new ArrayList<>(); searchVertex(vertex, entry.getValue(), tempLongestPath); if (tempLongestPath.size() > longestPath.size()) { longestPath = new ArrayList<>(tempLongestPath); } } if (longestPath.size() < 2) { System.out.println("NIE"); return; } Collections.sort(longestPath); System.out.println(longestPath.size()); int size = longestPath.size(); for (int i=0; i<size; i++) { System.out.print(longestPath.get(i) + 1); if(i < size-1) { System.out.print(" "); } } } private void searchVertex(int vertex, int paths, List<Integer> tempLongestPath) { if (visitedVertex.contains(vertex)) { return; } if (paths < minNumberOfPathsFromCity) { visitedVertex.add(vertex); return; } visitedVertex.add(vertex); for (int i = 0; i < vertex; i++) { if (cityConnections[vertex][i] == 1) { searchVertex(i, cityWithNumberOfPaths.getOrDefault(i, 0), tempLongestPath); } } for (int i = vertex + 1; i < numberOfCities; i++) { if (cityConnections[i][vertex] == 1) { searchVertex(i, cityWithNumberOfPaths.getOrDefault(i, 0), tempLongestPath); } } tempLongestPath.add(vertex); } private static Map sortByValue(Map unsortMap) { List list = new LinkedList(unsortMap.entrySet()); Collections.sort(list, new Comparator() { public int compare(Object o1, Object o2) { return ((Comparable) ((Map.Entry) (o2)).getValue()) .compareTo(((Map.Entry) (o1)).getValue()); } }); Map sortedMap = new LinkedHashMap(); for (Iterator it = list.iterator(); it.hasNext(); ) { Map.Entry entry = (Map.Entry) it.next(); sortedMap.put(entry.getKey(), entry.getValue()); } return sortedMap; } private void readValuesFromCommandLine() { Scanner sc = new Scanner(System.in); String[] firstLineParameters = sc.nextLine().split(" "); numberOfCities = Integer.parseInt(firstLineParameters[0]); minNumberOfPathsFromCity = Integer.parseInt(firstLineParameters[2]); cityConnections = new int[numberOfCities][numberOfCities]; while (sc.hasNext()) { String[] betweenCitiesPath = sc.nextLine().split(" "); int cityA = Integer.parseInt(betweenCitiesPath[0]) - 1; int cityB = Integer.parseInt(betweenCitiesPath[1]) - 1; if (cityA > cityB) { cityConnections[cityA][cityB] = 1; cityWithNumberOfPaths.put(cityA, cityWithNumberOfPaths.getOrDefault(cityA, 0) + 1); cityWithNumberOfPaths.put(cityB, cityWithNumberOfPaths.getOrDefault(cityB, 0) + 1); } else { cityConnections[cityB][cityA] = 1; cityWithNumberOfPaths.put(cityA, cityWithNumberOfPaths.getOrDefault(cityA, 0) + 1); cityWithNumberOfPaths.put(cityB, cityWithNumberOfPaths.getOrDefault(cityB, 0) + 1); } } cityWithNumberOfPaths = sortByValue(cityWithNumberOfPaths); } }
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | import java.util.*; public class mis { private int numberOfCities; private int minNumberOfPathsFromCity; private int[][] cityConnections; private Set<Integer> visitedVertex = new HashSet<>(); private List<Integer> longestPath = new ArrayList<>(); private Map<Integer, Integer> cityWithNumberOfPaths = new HashMap<>(); public static void main(String[] args) { mis mistrzostwa = new mis(); mistrzostwa.readValuesFromCommandLine(); mistrzostwa.findCities(); System.exit(0); } private void findCities() { Iterator<Map.Entry<Integer, Integer>> it = cityWithNumberOfPaths.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); int vertex = entry.getKey(); List<Integer> tempLongestPath = new ArrayList<>(); searchVertex(vertex, entry.getValue(), tempLongestPath); if (tempLongestPath.size() > longestPath.size()) { longestPath = new ArrayList<>(tempLongestPath); } } if (longestPath.size() < 2) { System.out.println("NIE"); return; } Collections.sort(longestPath); System.out.println(longestPath.size()); int size = longestPath.size(); for (int i=0; i<size; i++) { System.out.print(longestPath.get(i) + 1); if(i < size-1) { System.out.print(" "); } } } private void searchVertex(int vertex, int paths, List<Integer> tempLongestPath) { if (visitedVertex.contains(vertex)) { return; } if (paths < minNumberOfPathsFromCity) { visitedVertex.add(vertex); return; } visitedVertex.add(vertex); for (int i = 0; i < vertex; i++) { if (cityConnections[vertex][i] == 1) { searchVertex(i, cityWithNumberOfPaths.getOrDefault(i, 0), tempLongestPath); } } for (int i = vertex + 1; i < numberOfCities; i++) { if (cityConnections[i][vertex] == 1) { searchVertex(i, cityWithNumberOfPaths.getOrDefault(i, 0), tempLongestPath); } } tempLongestPath.add(vertex); } private static Map sortByValue(Map unsortMap) { List list = new LinkedList(unsortMap.entrySet()); Collections.sort(list, new Comparator() { public int compare(Object o1, Object o2) { return ((Comparable) ((Map.Entry) (o2)).getValue()) .compareTo(((Map.Entry) (o1)).getValue()); } }); Map sortedMap = new LinkedHashMap(); for (Iterator it = list.iterator(); it.hasNext(); ) { Map.Entry entry = (Map.Entry) it.next(); sortedMap.put(entry.getKey(), entry.getValue()); } return sortedMap; } private void readValuesFromCommandLine() { Scanner sc = new Scanner(System.in); String[] firstLineParameters = sc.nextLine().split(" "); numberOfCities = Integer.parseInt(firstLineParameters[0]); minNumberOfPathsFromCity = Integer.parseInt(firstLineParameters[2]); cityConnections = new int[numberOfCities][numberOfCities]; while (sc.hasNext()) { String[] betweenCitiesPath = sc.nextLine().split(" "); int cityA = Integer.parseInt(betweenCitiesPath[0]) - 1; int cityB = Integer.parseInt(betweenCitiesPath[1]) - 1; if (cityA > cityB) { cityConnections[cityA][cityB] = 1; cityWithNumberOfPaths.put(cityA, cityWithNumberOfPaths.getOrDefault(cityA, 0) + 1); cityWithNumberOfPaths.put(cityB, cityWithNumberOfPaths.getOrDefault(cityB, 0) + 1); } else { cityConnections[cityB][cityA] = 1; cityWithNumberOfPaths.put(cityA, cityWithNumberOfPaths.getOrDefault(cityA, 0) + 1); cityWithNumberOfPaths.put(cityB, cityWithNumberOfPaths.getOrDefault(cityB, 0) + 1); } } cityWithNumberOfPaths = sortByValue(cityWithNumberOfPaths); } } |