fork download
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  4.  
  5. public class Main {
  6. public static void main(String[] args) {
  7. String[] strings = {
  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. // Vertex v = new Vertex();
  38. final int N = strings.length;
  39. boolean ll[][] = new boolean[N][N];
  40.  
  41. List<SEOfString> cities = new ArrayList<>();
  42.  
  43. for (String city :
  44. strings) {
  45. cities.add(new SEOfString(city));
  46. }
  47. GraphSEOfString g = new GraphSEOfString(N);
  48. for (SEOfString city :
  49. cities) {
  50. g.addVertex(city);
  51. }
  52.  
  53. int indexOfCityWithMaximalDepth = 0;
  54. Vertex<SEOfString>[] biggestVertexes = g.dfs(0);
  55. for (int i = 1; i < strings.length; i++) {
  56. Vertex<SEOfString>[] currentVertexes = g.dfs(i);
  57. if (biggestVertexes.length < currentVertexes.length) {
  58. indexOfCityWithMaximalDepth = i;
  59. biggestVertexes = currentVertexes;
  60. }
  61. }
  62.  
  63. System.out.println("Самая большая последовательность у города \"" + strings[indexOfCityWithMaximalDepth] + "\"" + " c " + biggestVertexes.length + " городами");
  64. displayCHEEKYBREEKY(biggestVertexes);
  65. }
  66. public static void displayCHEEKYBREEKY(Vertex<SEOfString>[] toDisplay){
  67. System.out.print("[Размер последовательности равен " +toDisplay.length + "] "+toDisplay[0].label.getCity());
  68. for (int i = 1; i < toDisplay.length; i++) {
  69. System.out.print(" \u2192 " + toDisplay[i].label.getCity());
  70. }
  71. System.out.println("\n");
  72. }
  73. }
  74.  
  75. /**
  76.  * Start and end chars of string
  77.  */
  78. class SEOfString {
  79. private static final char[] charsToExcept = {
  80. 'ь'
  81. };
  82. private char start;
  83. private char end;
  84. private String city;
  85.  
  86. /**
  87.   * Получает первый и последний символ по входящему аргументу в параметр city
  88.   *
  89.   * @param city
  90.   */
  91. SEOfString(String city) {
  92. start = Character.toLowerCase(city.charAt(0));
  93. int lastIndex = city.length() - 1;
  94. while (isExceptionChar(city.charAt(lastIndex))) {
  95. lastIndex--;
  96. }
  97. end = city.charAt(lastIndex);
  98. this.city = city;
  99. }
  100.  
  101. boolean connectEnd(SEOfString string) {
  102. return (this.end == string.start) ? true : false;
  103. }
  104.  
  105. boolean connectStart(SEOfString string) {
  106. return (this.start == string.end) ? true : false;
  107. }
  108.  
  109. /**
  110.   * @param symbol
  111.   * @return
  112.   */
  113. private boolean isExceptionChar(char symbol) {
  114. for (char illegalChar :
  115. charsToExcept) {
  116. if (symbol == illegalChar) {
  117. return true;
  118. }
  119. }
  120. return false;
  121. }
  122.  
  123. public char getEnd() {
  124. return end;
  125. }
  126.  
  127. public char getStart() {
  128. return start;
  129. }
  130.  
  131. public String getCity() {
  132. return city;
  133. }
  134.  
  135. @Override
  136. public boolean equals(Object o) {
  137. if (this == o) return true;
  138. if (o == null || getClass() != o.getClass()) return false;
  139.  
  140. SEOfString that = (SEOfString) o;
  141.  
  142. if (start != that.start) return false;
  143. if (end != that.end) return false;
  144. return city.equals(that.city);
  145.  
  146. }
  147.  
  148. @Override
  149. public int hashCode() {
  150. int result = (int) start;
  151. result = 31 * result + (int) end;
  152. result = 31 * result + city.hashCode();
  153. return result;
  154. }
  155.  
  156. @Override
  157. public String toString() {
  158. return "SEOfString{" +
  159. "start=" + start +
  160. ", end=" + end +
  161. ", city='" + city + '\'' +
  162. '}';
  163. }
  164. }
  165.  
  166. class Vertex<T> {
  167. public T label;
  168. public boolean wasVisited;
  169.  
  170. public Vertex(T label) {
  171. wasVisited = false;
  172. this.label = label;
  173. }
  174.  
  175. @Override
  176. public String toString() {
  177. return "Vertex{" +
  178. "label=" + label +
  179. ", wasVisited=" + wasVisited +
  180. '}';
  181. }
  182. }
  183.  
  184. class Graph<T> {
  185. protected final ArrayList<Vertex<T>> vertexList;
  186. protected final boolean[][] adjMat;
  187. protected final Stack<Integer> stack;
  188.  
  189. public Graph(int N) {
  190. vertexList = new ArrayList<>();
  191. adjMat = new boolean[N][N];
  192. stack = new Stack<>();
  193. }
  194.  
  195. public void addVertex(T vertex) {
  196. vertexList.add(new Vertex<T>(vertex));
  197. }
  198.  
  199. public void addEdge(int start, int end) {
  200. adjMat[start][end] = true;
  201. }
  202.  
  203. public void displayVertex(int v) {
  204. System.out.println(vertexList.get(v));
  205. }
  206.  
  207. public Vertex<T>[] dfs(int i) {
  208. vertexList.get(i).wasVisited = true;
  209. Stack<T> maximalStack = new Stack<>();
  210. int maxNOfCities = 1, currentNOfCities = 1;
  211. stack.push(i);
  212. while (!stack.isEmpty()) {
  213. int v = getAdjUnvisitedVertex(stack.peek());
  214. if (v == -1) {
  215. if (currentNOfCities > maxNOfCities) {
  216. maxNOfCities = currentNOfCities;
  217. maximalStack = (Stack<T>) stack.clone();
  218. }
  219. currentNOfCities--;
  220. stack.pop();
  221. } else {
  222. currentNOfCities++;
  223. vertexList.get(v).wasVisited = true;
  224. stack.push(v);
  225. }
  226. }
  227. for (Vertex v : vertexList) {
  228. v.wasVisited = false;
  229. }
  230. Vertex<T>[] maxD = new Vertex[maximalStack.size()];
  231. while (!maximalStack.isEmpty()) {
  232. maxD[maximalStack.size() - 1] = vertexList.get((Integer) maximalStack.peek());
  233. maximalStack.pop();
  234. }
  235. return maxD;
  236. }
  237.  
  238. protected int getAdjUnvisitedVertex(int peek) {
  239. for (int i = 0; i < vertexList.size(); i++) {
  240. if (adjMat[peek][i] && !vertexList.get(i).wasVisited) {
  241. return i;
  242. }
  243. }
  244. return -1;
  245. }
  246. }
  247.  
  248. class GraphSEOfString extends Graph<SEOfString> {
  249.  
  250. public GraphSEOfString(int N) {
  251. super(N);
  252. }
  253.  
  254. @Override
  255. public void addVertex(SEOfString newCity) {
  256. super.addVertex(newCity);
  257. for (int i = 0; i < vertexList.size() - 1; i++) {
  258. SEOfString string = vertexList.get(i).label;
  259. if (newCity.connectEnd(string)) {
  260. adjMat[vertexList.size() - 1][i] = true;
  261. } else if (newCity.connectStart(string)) {
  262. adjMat[i][vertexList.size() - 1] = true;
  263. }
  264. }
  265. }
  266. }
Success #stdin #stdout 0.12s 320832KB
stdin
Standard input is empty
stdout
Самая большая последовательность у города "Тьмутаракань" c 18 городами
[Размер последовательности равен 18] Тьмутаракань → Начало → Орёл → Липецк → Кишенёв → Владимир → Рига → Астана → Астрахань → Норильск → Киров → Воронеж → Житомир → Ростов → Волгоград → Донецк → Каракум → Москва