Do deep search using a stack

The procedure should look something like this:

Note that there is a restriction there: Only visited nodes can enter the stack. This means that else if at the end is a violation of this restriction. More than that, it's a violation of the heap concept, where you're trying to remove an element from the middle of the stack instead of removing it from the top. That remove should not be there.

Class java.util.Stack inherits remove(int) method % of java.util.Vector . This method does not do what you expect it to do. It will not remove the topo element from the stack. Instead, it will interpret topo as being the position of the element to be removed. This will totally mess up your stack.

In addition, it is not recommended to use the java.util.Stack class because of the many design flaws it has (mainly inheriting from Vector ). See more about this here / a>. Ideally you implement your own stack (I'll give it a different name to avoid confusion):

import java.util.NoSuchElementException;

public interface Pilha<T> {
    public T top() throws NoSuchElementException;
    public T pop() throws NoSuchElementException;
    public void push(T element);
    public boolean isEmpty();
}

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class PilhaArrayList<T> implements Pilha<T> {
    private final List<T> elementos;

    public PilhaArrayList() {
        this.elementos = new ArrayList<>();
    }

    @Override
    public T top() throws NoSuchElementException {
         if (isEmpty()) throw new NoSuchElementException();
         return elementos.get(elementos.size() - 1);
    }

    @Override
    public T pop() throws NoSuchElementException {
         if (isEmpty()) throw new NoSuchElementException();
         return elementos.remove(elementos.size() - 1);
    }

    @Override
    public void push(T element) {
        elementos.add(element);
    }

    @Override
    public boolean isEmpty() {
        return elementos.isEmpty();
    }
}

Your code should look like this:

    public void pilhaDFS(int s) {
        boolean[] visitados = new boolean[n];
        visitados[s] = true;
        Pilha<Integer> pilha = new PilhaArrayList<>();
        pilha.push(s);
        while (!pilha.isEmpty()) {
            int topo = pilha.pop();
            for (int linha : arestas[s]) {
                if (visitados[linha]) continue;
                System.out.println(s + ">>" + linha);
                visitados[linha] = true;
                pilha.push(linha);
            }
        }
    }

Note that the value of the gatilho variable was never read anywhere, and therefore was useless. The% of% that accompanied the break was harmful because it prevented his search to return a few steps and to try to go another way as soon as he found the first "dead end". Initializing the array gatilho with all visitados is unnecessary since every array of false is already created with boolean in all positions.

Finally, it's a good idea to follow code conventions for respect the nomenclature of variables.

Looking at the rest of the code, generic types and arrays do not go well together. I suggest modeling the edges with adjacency list:

private final Map<Integer, List<Integer>> arestas;

Your class code looks like this:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public Grafo {
    private final Map<Integer, List<Integer>> arestas;
    private final int n;
    private int qtdArestas = 0;

    public Grafo(int n) {
        this.n = n;
        arestas = new HashMap<>();
    }

    public void adicionaAresta(int origem, int destino) {
        List<Integer> adjacencias = arestas.get(origem);
        if (adjacencias == null) {
            adjacencias = new ArrayList<>();
            arestas.put(origem, adjacencias);
        }
        adjacencias.add(destino);
        qtdArestas++;
    }

    // Resto da classe.
}

The false method I showed above would look almost the same. The only change is that pilhaDFS would arestas[s] .

Your arestas.get(s) methods would look like this:

    private int dfs(int s, boolean[] visited, int contador) {
        if (visited[s]) return contador;
        contador++;
        visited[s] = true;
        for (int n : arestas.get(s)) {
            System.out.println(s + ">>" + n);
            contador = dfs(n, visited, contador);
        }
        return contador;
    }

    public void dfs(int s) {
        int b = dfs(s, new boolean[n], 0);
        System.out.println(contador);
    }

Note that dfs with multiple parameters is private.