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<StartEndAndStringOfCity> cities = new ArrayList<>();
  42.  
  43.         for (String city :
  44.                 strings) {
  45.             cities.add(new StartEndAndStringOfCity(city));
  46.         }
  47.         GraphForSooqaBlyatPidoraha g = new GraphForSooqaBlyatPidoraha(N);
  48.         for (StartEndAndStringOfCity city :
  49.                 cities) {
  50.             g.addVertex(city);
  51.         }
  52.  
  53.         int indexOfCityWithMaximalDepth = 0;
  54.         Vertex<StartEndAndStringOfCity>[] biggestVertexes = g.getMaxSequence(0);
  55.         for (int i = 1; i < strings.length; i++) {
  56.             Vertex<StartEndAndStringOfCity>[] currentVertexes = g.getMaxSequence(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<StartEndAndStringOfCity>[] 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 StartEndAndStringOfCity {
  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.     StartEndAndStringOfCity(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 canConnectToEnd(StartEndAndStringOfCity string) {
  102.         return (this.end == string.start) ? true : false;
  103.     }
  104.  
  105.     boolean canConnectToStart(StartEndAndStringOfCity 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 String toString() {
  137.         return "StartEndAndStringOfCity{" +
  138.                 "start=" + start +
  139.                 ", end=" + end +
  140.                 ", city='" + city + '\'' +
  141.                 '}';
  142.     }
  143. }
  144.  
  145. class Vertex<T> {
  146.     public T label;
  147.     public boolean wasVisited;
  148.  
  149.     public Vertex(T label) {
  150.         wasVisited = false;
  151.         this.label = label;
  152.     }
  153.  
  154.     @Override
  155.     public String toString() {
  156.         return "Vertex{" +
  157.                 "label=" + label +
  158.                 ", wasVisited=" + wasVisited +
  159.                 '}';
  160.     }
  161. }
  162.  
  163. class Graph<T> {
  164.     protected final ArrayList<Vertex<T>> vertexList;
  165.     protected final boolean[][] adjMat;
  166.     protected final Stack<Integer> stack;
  167.  
  168.     public Graph(int N) {
  169.         vertexList = new ArrayList<>();
  170.         adjMat = new boolean[N][N];
  171.         stack = new Stack<>();
  172.     }
  173.  
  174.     public void addVertex(T vertex) {
  175.         vertexList.add(new Vertex<T>(vertex));
  176.     }
  177.  
  178.     public void addEdge(int start, int end) {
  179.         adjMat[start][end] = true;
  180.     }
  181.  
  182.     public void displayVertex(int v) {
  183.         System.out.println(vertexList.get(v));
  184.     }
  185.  
  186.     public Vertex<T>[] getMaxSequence(int i) {
  187.         vertexList.get(i).wasVisited = true;
  188.         Stack<T> maximalStack = new Stack<>();
  189.         int maxSequence = 1, currentSequence = 1;
  190.         stack.push(i);
  191.         while (!stack.isEmpty()) {
  192.             int v = getAdjUnvisitedVertex(stack.peek());
  193.             if (v == -1) {
  194.                 if (currentSequence > maxSequence) {
  195.                     maxSequence = currentSequence;
  196.                     maximalStack = (Stack<T>) stack.clone();
  197.                 }
  198.                 currentSequence--;
  199.                 stack.pop();
  200.             } else {
  201.                 currentSequence++;
  202.                 vertexList.get(v).wasVisited = true;
  203.                 stack.push(v);
  204.             }
  205.         }
  206.         for (Vertex v : vertexList) {
  207.             v.wasVisited = false;
  208.         }
  209.         Vertex<T>[] maxD = new Vertex[maximalStack.size()];
  210.         while (!maximalStack.isEmpty()) {
  211.             maxD[maximalStack.size() - 1] = vertexList.get((Integer) maximalStack.peek());
  212.             maximalStack.pop();
  213.         }
  214.         return maxD;
  215.     }
  216.  
  217.     protected int getAdjUnvisitedVertex(int peek) {
  218.         for (int i = 0; i < vertexList.size(); i++) {
  219.             if (adjMat[peek][i] && !vertexList.get(i).wasVisited) {
  220.                 return i;
  221.             }
  222.         }
  223.         return -1;
  224.     }
  225. }
  226.  
  227. class GraphForSooqaBlyatPidoraha extends Graph<StartEndAndStringOfCity> {
  228.  
  229.     public GraphForSooqaBlyatPidoraha(int N) {
  230.         super(N);
  231.     }
  232.  
  233.     @Override
  234.     public void addVertex(StartEndAndStringOfCity newCity) {
  235.         super.addVertex(newCity);
  236.         for (int i = 0; i < vertexList.size() - 1; i++) {
  237.             StartEndAndStringOfCity string = vertexList.get(i).label;
  238.             if (newCity.canConnectToEnd(string)) {
  239.                 adjMat[vertexList.size() - 1][i] = true;
  240.             } else if (newCity.canConnectToStart(string)) {
  241.                 adjMat[i][vertexList.size() - 1] = true;
  242.             }
  243.         }
  244.     }
  245. }
Success #stdin #stdout 0.14s 320832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Самая большая последовательность у города "Тьмутаракань" c 18 городами
[Размер последовательности равен 18] Тьмутаракань → Начало → Орёл → Липецк → Кишенёв → Владимир → Рига → Астана → Астрахань → Норильск → Киров → Воронеж → Житомир → Ростов → Волгоград → Донецк → Каракум → Москва
https://ideone.com/Q41tWs
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!