Why doesn't this solution work?

Question

Algorithms

Task: determine if there is a negative cycle in the graph. What emaxx offers. I decided to act a little differently: find a cycle in the graph and check its weight. Here is the program:

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");
  }
}

On which graph does she stumble if she fails the 24th test?
The task itself.

Answer 1

You have a simple DFS. If he is not lucky to go not along a negative cycle, but at the same time bypass some of its vertices, then you will screw up the enumeration and this cycle will never be found.
In order to find a negative cycle through DFS, you will have to go through ALL cycles. To do this, do not mark the vertices as visited. True, it will work very slowly and will almost certainly not pass the time limit, because there can be an exponentially many cycles in the harp.
Edit, here's an example. There is only one negative cycle in the graph 1->2->3->1. But there is also an edge 1->3. If you start from vertex 1, then take edge 1->3, then you can’t go anywhere from vertex 3, remove it from the stack and mark it as visited. Next you'll look at edge 1->2 and then from vertex 2 you will skip edge 2->3 because vertex 3 has already been visited.
This example can be infinitely more complicated - it all depends on the order in which the edges at each vertex will be bypassed.