fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Самая большая последовательность у города "Тьмутаракань" c 18 городами
[Размер последовательности равен 18] Тьмутаракань → Начало → Орёл → Липецк → Кишенёв → Владимир → Рига → Астана → Астрахань → Норильск → Киров → Воронеж → Житомир → Ростов → Волгоград → Донецк → Каракум → Москва
https://ideone.com/qOUEZA
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!