import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
public static void main
(String[] args
) { "Москва",
"Саратов",
"Свердловск",
"Астана",
"Астрахань",
"Санкт-петербург",
"Гурьев",
"Начало",
"Орёл",
"Липецк",
"Кишенёв",
"Владимир",
"Ростов",
"Воронеж",
"Житомир",
"Минск",
"Киров",
"Норильск",
"Муром",
"Донецк",
"Тьмутаракань",
"Омск",
"Каракум",
"Волгоград",
"Уфа",
"Тарту",
"Рига",
"Юрмола"
};
// Vertex v = new Vertex();
final int N = strings.length;
boolean ll[][] = new boolean[N][N];
List<SEOfString> cities = new ArrayList<>();
strings) {
cities.add(new SEOfString(city));
}
GraphSEOfString g = new GraphSEOfString(N);
for (SEOfString city :
cities) {
g.addVertex(city);
}
int indexOfCityWithMaximalDepth = 0;
Vertex<SEOfString>[] biggestVertexes = g.dfs(0);
for (int i = 1; i < strings.length; i++) {
Vertex<SEOfString>[] currentVertexes = g.dfs(i);
if (biggestVertexes.length < currentVertexes.length) {
indexOfCityWithMaximalDepth = i;
biggestVertexes = currentVertexes;
}
}
System.
out.
println("Самая большая последовательность у города \"" + strings
[indexOfCityWithMaximalDepth
] + "\"" + " c " + biggestVertexes.
length + " городами"); displayCHEEKYBREEKY(biggestVertexes);
}
public static void displayCHEEKYBREEKY(Vertex<SEOfString>[] toDisplay){
System.
out.
print("[Размер последовательности равен " +toDisplay.
length + "] "+toDisplay
[0].
label.
getCity()); for (int i = 1; i < toDisplay.length; i++) {
System.
out.
print(" \u2192 " + toDisplay
[i
].
label.
getCity()); }
}
}
/**
* Start and end chars of string
*/
class SEOfString {
private static final char[] charsToExcept = {
'ь'
};
private char start;
private char end;
/**
* Получает первый и последний символ по входящему аргументу в параметр city
*
* @param city
*/
start
= Character.
toLowerCase(city.
charAt(0)); int lastIndex = city.length() - 1;
while (isExceptionChar(city.charAt(lastIndex))) {
lastIndex--;
}
end = city.charAt(lastIndex);
this.city = city;
}
boolean connectEnd(SEOfString string) {
return (this.end == string.start) ? true : false;
}
boolean connectStart(SEOfString string) {
return (this.start == string.end) ? true : false;
}
/**
* @param symbol
* @return
*/
private boolean isExceptionChar(char symbol) {
for (char illegalChar :
charsToExcept) {
if (symbol == illegalChar) {
return true;
}
}
return false;
}
public char getEnd() {
return end;
}
public char getStart() {
return start;
}
return city;
}
@Override
public boolean equals
(Object o
) { if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
SEOfString that = (SEOfString) o;
if (start != that.start) return false;
if (end != that.end) return false;
return city.equals(that.city);
}
@Override
public int hashCode() {
int result = (int) start;
result = 31 * result + (int) end;
result = 31 * result + city.hashCode();
return result;
}
@Override
return "SEOfString{" +
"start=" + start +
", end=" + end +
", city='" + city + '\'' +
'}';
}
}
class Vertex<T> {
public T label;
public boolean wasVisited;
public Vertex(T label) {
wasVisited = false;
this.label = label;
}
@Override
return "Vertex{" +
"label=" + label +
", wasVisited=" + wasVisited +
'}';
}
}
class Graph<T> {
protected final ArrayList<Vertex<T>> vertexList;
protected final boolean[][] adjMat;
protected final Stack<Integer> stack;
public Graph(int N) {
vertexList = new ArrayList<>();
adjMat = new boolean[N][N];
stack = new Stack<>();
}
public void addVertex(T vertex) {
vertexList.add(new Vertex<T>(vertex));
}
public void addEdge(int start, int end) {
adjMat[start][end] = true;
}
public void displayVertex(int v) {
System.
out.
println(vertexList.
get(v
)); }
public Vertex<T>[] dfs(int i) {
vertexList.get(i).wasVisited = true;
Stack<T> maximalStack = new Stack<>();
int maxNOfCities = 1, currentNOfCities = 1;
stack.push(i);
while (!stack.isEmpty()) {
int v = getAdjUnvisitedVertex(stack.peek());
if (v == -1) {
if (currentNOfCities > maxNOfCities) {
maxNOfCities = currentNOfCities;
maximalStack = (Stack<T>) stack.clone();
}
currentNOfCities--;
stack.pop();
} else {
currentNOfCities++;
vertexList.get(v).wasVisited = true;
stack.push(v);
}
}
for (Vertex v : vertexList) {
v.wasVisited = false;
}
Vertex<T>[] maxD = new Vertex[maximalStack.size()];
while (!maximalStack.isEmpty()) {
maxD
[maximalStack.
size() - 1] = vertexList.
get((Integer) maximalStack.
peek()); maximalStack.pop();
}
return maxD;
}
protected int getAdjUnvisitedVertex(int peek) {
for (int i = 0; i < vertexList.size(); i++) {
if (adjMat[peek][i] && !vertexList.get(i).wasVisited) {
return i;
}
}
return -1;
}
}
class GraphSEOfString extends Graph<SEOfString> {
public GraphSEOfString(int N) {
super(N);
}
@Override
public void addVertex(SEOfString newCity) {
super.addVertex(newCity);
for (int i = 0; i < vertexList.size() - 1; i++) {
SEOfString string = vertexList.get(i).label;
if (newCity.connectEnd(string)) {
adjMat[vertexList.size() - 1][i] = true;
} else if (newCity.connectStart(string)) {
adjMat[i][vertexList.size() - 1] = true;
}
}
}
}