// --------------
// DFSearch1.java
// --------------

import java.util.Arrays;

final class DFSearch {
    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    private static boolean eval (int[][] g, int u, int v, boolean[] b) {
        if (u == v)
            return true;
        b[u] = true;
        for (int w : g[u]) {
            if (!b[w] && eval(g, w, v, b))
                return true;}
        return false;}

    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v) {
        final boolean[] b = new boolean[g.length];
        return eval(g, u, v, b);}

    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    private static boolean eval (int[][] g, int u, int v, GraphVisitor x, boolean[] b) {
        if (u == v) {
            x.visit(u, -1);
            return true;}
        b[u] = true;
        for (int w : g[u]) {
            if (!b[w] && eval(g, w, v, x, b)) {
                x.visit(u, -1);
                return true;}}
        return false;}

    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v, GraphVisitor x) {
        final boolean[] b = new boolean[g.length];
        return eval(g, u, v, x, b);}}

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

        final int[][] g = { // Fig. 14.30, Pg. 500
            {1, 3},         // 0
            {3, 4},         // 1
            {0, 3, 5},      // 2
            {4, 5, 6},      // 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 GraphVertexVisitor x = new GraphVertexVisitor();
        assert DFSearch.eval(g, 0, 5, x) == true;
        assert x.path().equals(Arrays.asList(0, 1, 3, 4, 6, 5));
        }

        {
        final GraphVertexVisitor x = new GraphVertexVisitor();
        assert DFSearch.eval(g, 3, 6, x) == true;
        assert x.path().equals(Arrays.asList(3, 4, 6));
        }

        {
        final GraphLengthVisitor x = new GraphLengthVisitor();
        assert DFSearch.eval(g, 0, 5, x) == true;
        assert x.pathLength() == 6;
        }

        {
        final GraphLengthVisitor x = new GraphLengthVisitor();
        assert DFSearch.eval(g, 3, 6, x) == true;
        assert x.pathLength() == 3;
        }

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