// ------------
// DFTSort.java
// ------------

import java.util.Arrays;

final class DFTSort {
    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    private static void eval (int[][] g, GraphVisitor gv, boolean[] b, int u) {
        b[u] = true;
        for (int v : g[u])
            if (!b[v])
                eval(g, gv, b, v);
        gv.visit(u, -1);}

    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    public static void eval (int[][] g, GraphVisitor gv) {
        final boolean[] b = new boolean[g.length];
        for (int u = 0; u != g.length; ++u)
            if (!b[u])
                eval(g, gv, b, u);}}

final class DFTSortTest {
    public static void main (String[] args) {
        System.out.println("DFTSort.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

        {
        final GraphVertexVisitor gvv = new GraphVertexVisitor();
        DFTSort.eval(g, gvv);
        assert gvv.path().equals(Arrays.asList(2, 0, 1, 3, 4, 6, 5));
        }

        {
        final GraphLengthVisitor glv = new GraphLengthVisitor();
        DFTSort.eval(g, glv);
        assert glv.pathLength() == 7;
        }

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