//二分图检测
public class BipartitionDetection {
    private Graph G;
    private boolean[] visited;
    private int[] colors;
    private boolean isBipartite = true;

    public BipartitionDetection(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        colors = new int[G.V()];

        for(int i=0;i<G.V();i++) colors[i] = -1;

        // 多包一层for，防止有多个联通分量
        for(int v = 0 ;v<G.V();v++){
            if(!visited[v])
                if(!dfs(v,0)) {
                    isBipartite = false;break;
                }
        }
    }

    // 深度优先遍历
    private boolean dfs(int v,int color){
        visited[v] = true;
        colors[v] = color;
        // 遍历相邻节点
        for(int w : G.adj(v)){
            if(!visited[w]){
                if(!dfs(w,1-color)) return false;   // 遍历下一个点，染不同颜色
            }
            else if(colors[w] == colors[v]) return false;   // 如果相邻被访问过且相等，则是同一颜色，不是二分图。二分图边的两点隶属于不同的2部分
        }
        return true;
    }

    public boolean isBipartite(){
        return isBipartite;
    }


    public static void main(String[] args){

        Graph g = new Graph("g2.txt");
        BipartitionDetection bipartitionDetection = new BipartitionDetection(g);
        System.out.println(bipartitionDetection.isBipartite());
    }
}