Задача: определить, есть ли в графе отрицательный цикл.
Что предлагает emaxx. Я решил действовать немного по-другому: находить цикл в графе и проверять его вес. Вот программа:
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;
public class NegativeWeightCycle {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] graph = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
}
}
sc.close();
boolean[] visited = new boolean[n];
boolean[] inStack = new boolean[n];
//edgeTo[i] - вершина, из которой попали в i
int[] edgeTo = new int[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Deque<Integer> stack = new ArrayDeque<>();
stack.offerFirst(i);
while (!stack.isEmpty()) {
int v = stack.getFirst();
if (inStack[v]) {
v = stack.pollFirst();
inStack[v] = false;
continue;
}
//аналогичный подход при обыном обнаружении цкилов, только вместо покраски
//проверка, находится ли вершина в стеке (название пошло от рекурсивного дфс)
//а так испольщуются увета вершин
inStack[v] = true;
visited[v] = true;
for (int j = 0; j < n; j++) {
int dist = graph[v][j];
//100000 - значит ребра между вершинами нет
if (dist != 100000) {
if (inStack[j]) {
int from = edgeTo[j]; //для восстановелния, если цикл неотр.
edgeTo[j] = v;
int pathWeight = graph[v][j];
int iter = v;
while (iter != j) {
pathWeight += graph[edgeTo[iter]][iter];
iter = edgeTo[iter];
}
if (pathWeight < 0) {
System.out.println("YES");
return;
} else {
//восстановлние
edgeTo[j] = from;
}
} else if (!visited[j]) {
//возможно, помечать, что вершина в стеке логичнее здесь, но вроде
//не имеет разницы
stack.offerFirst(j);
edgeTo[j] = v;
}
}
}
}
}
}
System.out.println("NO");
}
}
На каком графе она спотыкается, если не может пройти 24-й тест?
Сама задача. 
