// --------------
// DFSearch2.java
// --------------

import java.util.Arrays;
import java.util.Stack;

final class DFSearch {
    /**
     * O(v)     in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v) {
        final boolean[]      b  = new boolean[g.length];
        final Stack<Integer> si = new Stack<Integer>();
        si.push(u);
        while (!si.isEmpty()) {
            final int t = si.pop();
            if (t == v)
                return true;
            if (!b[t]) {
                b[t] = true;
                for (int w : g[t])
                    si.push(w);}}
        return false;}

    /**
     * O(v)     in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v, GraphVisitor gv) {
        final boolean[]      b  = new boolean[g.length];
        final Stack<Integer> si = new Stack<Integer>();
        si.push(u);
        gv.visit(u, u);
        while (!si.isEmpty()) {
            final int t = si.pop();
            if (t == v)
                return true;
            if (!b[t]) {
                b[t] = true;
                for (int w : g[t]) {
                    si.push(w);
                    gv.visit(t, w);}}}
        return false;}}

final class DFSearch2Test {
    public static void main (String[] args) {
        System.out.println("DFSearch2.java");

        final int[][] g = { // Fig. 14.30, Pg. 500
            {3, 1},         // 0
            {4, 3},         // 1
            {5, 3, 0},      // 2
            {6, 5, 4},      // 3
            {6},            // 4
            {},             // 5
            {5}};           // 6

        assert DFSearch.eval(g, 0, 0) == true;
        assert DFSearch.eval(g, 0, 1) == true;
        assert DFSearch.eval(g, 0, 2) == false;
        assert DFSearch.eval(g, 0, 3) == true;
        assert DFSearch.eval(g, 0, 4) == true;
        assert DFSearch.eval(g, 0, 5) == true;
        assert DFSearch.eval(g, 0, 6) == true;

        assert DFSearch.eval(g, 3, 0) == false;
        assert DFSearch.eval(g, 3, 1) == false;
        assert DFSearch.eval(g, 3, 2) == false;
        assert DFSearch.eval(g, 3, 3) == true;
        assert DFSearch.eval(g, 3, 4) == true;
        assert DFSearch.eval(g, 3, 5) == true;
        assert DFSearch.eval(g, 3, 6) == true;

        assert DFSearch.eval(g, 6, 0) == false;
        assert DFSearch.eval(g, 6, 1) == false;
        assert DFSearch.eval(g, 6, 2) == false;
        assert DFSearch.eval(g, 6, 3) == false;
        assert DFSearch.eval(g, 6, 4) == false;
        assert DFSearch.eval(g, 6, 5) == true;
        assert DFSearch.eval(g, 6, 6) == true;

        {
        final GraphEdgeVisitor gev = new GraphEdgeVisitor(g.length);
        assert DFSearch.eval(g, 0, 5, gev) == true;
        assert Arrays.equals(gev.pred(), new int[]{0, 0, -1, 1, 3, 6, 4});
        assert gev.path(0, 5).equals(Arrays.asList(0, 1, 3, 4, 6, 5));
        }

        {
        final GraphEdgeVisitor gev = new GraphEdgeVisitor(g.length);
        assert DFSearch.eval(g, 3, 6, gev) == true;
        assert Arrays.equals(gev.pred(), new int[]{-1, -1, -1, 3, 3, 3, 4});
        assert gev.path(3, 6).equals(Arrays.asList(3, 4, 6));
        }

        System.out.println("Done.");}}