// https://leetcode.com/problems/is-graph-bipartite/

import java.util.*;
import java.io.*;

class BipartiteGraphUsingBFSandDFS {

    // BFS
    public static boolean bfs(int node, int color, int colorArray[], ArrayList<ArrayList<Integer>> adj){
        Queue<Integer> q = new LinkedList<>();

        q.add(node);
        colorArray[node] = color;

        while(!q.isEmpty()){
            Integer currNodeode = q.poll();

            for(Integer it : adj.get(currNodeode)){
                // if(!visited[it]){
                //     visited[it] = true;
                //     q.add(it);
                // }
                if (colorArray[it]==-1){ // not colored yet (not visited basically)
                    colorArray[it] = 1 - colorArray[currNodeode];
                    q.add(it);
                } else if (colorArray[it]==colorArray[currNodeode]){
                    return false;
                }
            }
        }

        return true;
    }


    // DFS
    public static boolean dfs(int node, int color, int colorArray[], ArrayList<ArrayList<Integer>> adj){
        colorArray[node] = color;

        for (Integer it: adj.get(node)){
            if (colorArray[it]==-1){ // not colored yet (not visited basically)
                if (dfs(it,1-color, colorArray, adj)==false) return false;
            } else if (colorArray[it]==color){
                return false;
            }
        }
        return true;
    }


    public static boolean isBipartite(int graph[][]){

        int V = graph.length;

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0;i<V;i++) adj.add(new ArrayList<>());

        for(int u=0; u<V; u++){
            for(int v : graph[u]){
                adj.get(u).add(v);
            }
        }

        int colorArray[] = new int[V];
        Arrays.fill(colorArray, -1);

        for(int i=0;i<V;i++){
            if(colorArray[i] == -1){

                // choose one
                if(dfs(i, 0, colorArray, adj)==false) return false;
                // if(!bfs(i, 0, colorArray, adj)) return false;
            }
        }

        return true;
    }


    //  DRIVER
    public static void main(String args[]){

        // ============ CASE 1 ============
        {
            int graph[][] = {
                {1,2,3},
                {0,2},
                {0,1,3},
                {0,2}
            };

            System.out.printf("Case 1: %s\n",
                isBipartite(graph) ? "Bipartite" : "Not Bipartite");
        }

        // ============ CASE 2 ============
        {
            int graph[][] = {
                {1,3},
                {0,2},
                {1,3},
                {0,2}
            };

            System.out.printf("Case 2: %s\n",
                isBipartite(graph) ? "Bipartite" : "Not Bipartite");
        }

        // ============ CASE 3 ============
        {
            int graph[][] = {
                {1},
                {0,2},
                {1,3},
                {2}
            };

            System.out.printf("Case 3: %s\n",
                isBipartite(graph) ? "Bipartite" : "Not Bipartite");
        }

        // ============ CASE 4 ============
        {
            int graph[][] = {
                {},
                {},
                {}
            };

            System.out.printf("Case 4: %s\n",
                isBipartite(graph) ? "Bipartite" : "Not Bipartite");
        }
    }
}