// ------------------
// DFIsBipartite.java
// ------------------

import java.util.Arrays;

enum Color {white, red, black}

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

    /**
     * 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)
            if (c[u] == Color.white) {
                c[u] = Color.red;
                if (!eval(g, c, u))
                    return false;}
        return true;}}

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

        {
        final int[][] g = {
            {1},  // 0
            {0}}; // 1
        assert DFIsBipartite.eval(g);
        }

        {
        final int[][] g = {
            {1},  // 0
            {2},  // 1
            {0}}; // 2
        assert !DFIsBipartite.eval(g);
        }
        {
        final int[][] g = {
            {1},  // 0
            {2},  // 1
            {3},  // 2
            {0}}; // 3
        assert DFIsBipartite.eval(g);
        }

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