package leetcode;

/**
 * https://leetcode.com/problems/possible-bipartition/
 */
public class Problem886 {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        // TODO
        return false;
    }

    public static void main(String[] args) {
        Problem886 prob = new Problem886();
        System.out.println(prob.possibleBipartition(4, new int[][]{{1, 2}, {1, 3}, {2, 4}})); // true
        System.out.println(prob.possibleBipartition(3, new int[][]{{1, 2}, {1, 3}, {2, 3}})); // false
        System.out.println(prob.possibleBipartition(5, new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 5}})); // false
    }
}

@@ -12,16 +12,68 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A * h
@@ -231,457 +231,1177 @@
     
-// TODO%0A        return false;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem886 prob = new Problem886();%0A        System.out.println(prob.possibleBipartition(4, new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B1, 3%7D, %7B2, 4%7D%7D)); // true
+List%3CInteger%3E%5B%5D graph = new List%5BN + 1%5D;%0A        for (int i = 1; i %3C= N; i++) %7B%0A            graph%5Bi%5D = new ArrayList%3C%3E();%0A        %7D%0A        boolean%5B%5D visited = new boolean%5BN + 1%5D;%0A        for (int%5B%5D dislike : dislikes) %7B%0A            graph%5Bdislike%5B0%5D%5D.add(dislike%5B1%5D);%0A            graph%5Bdislike%5B1%5D%5D.add(dislike%5B0%5D);%0A        %7D%0A        boolean answer = true;%0A        // true -%3E black%0A        // false -%3E red%0A        boolean%5B%5D blackRed = new boolean%5BN + 1%5D;%0A        for (int i = 1; i %3C= N; i++) %7B%0A            if (!visited%5Bi%5D) %7B%0A                answer &= isBipartite(graph, visited, blackRed, i);%0A            %7D%0A        %7D%0A        return answer;
 %0A    
+%7D%0A%0A
     
-System.out.println(prob.possibleBipartition(3, new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B1, 3%7D, %7B2, 3%7D%7D)); // false%0A        System.out.println(prob.possibleBipartition(5, new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B4, 5%7D, %7B1, 5%7D%7D)); // false
+private static boolean isBipartite(List%3CInteger%3E%5B%5D graph, boolean%5B%5D visited, boolean%5B%5D blackRed, int n) %7B%0A        visited%5Bn%5D = true;%0A        boolean result = true;%0A        for (int adj : graph%5Bn%5D) %7B%0A            if (!visited%5Badj%5D) %7B%0A                blackRed%5Badj%5D = !blackRed%5Bn%5D;%0A                result &= isBipartite(graph, visited, blackRed, adj);%0A            %7D else %7B%0A                if (blackRed%5Bn%5D == blackRed%5Badj%5D) %7B%0A                    return false;%0A                %7D%0A            %7D%0A        %7D%0A        return result;
 %0A   

Solve problem 886