// ---------------
// DFHasCycle.java
// ---------------

import java.util.Arrays;

enum Color {white, gray, black}

final class DFHasCycle {
    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    private static boolean eval (int[][] g, Color[] c, int u) {
        c[u] = Color.gray;
        for (int v : g[u])
            switch (c[v]) {
                case white:
                    if (eval(g, c, v))
                        return true;
                    break;
                case gray:
                    return true;
                case black:
                    break;
                default:
                    assert false;}
        c[u] = Color.black;
        return false;}

    /**
     * O(v + e) in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g) {
        final Color[] c = new Color[g.length];
        Arrays.fill(c, Color.white);
        for (int u = 0; u != g.length; ++u) {
            assert c[u] != Color.gray;
            if (c[u] == Color.white)
                if (eval(g, c, u))
                    return true;}
        return false;}}

final class DFHasCycleTest {
    public static void main (String[] args) {
        System.out.println("DFHasCycle.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 !DFHasCycle.eval(g);
        }

        {
        final int[][] g = {
            {1, 3},         // 0
            {3, 4},         // 1
            {0, 5},         // 2
            {3, 4, 5, 6},   // 3
            {6},            // 4
            {},             // 5
            {5}};           // 6
        assert DFHasCycle.eval(g);
        }

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