> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/graph-ii/886.-possible-bipartition.md).

# 886. Possible Bipartition

````java
```java
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, List<Integer>> graph = buildGraph(dislikes);
        int[] color = new int[n+1]; // 0, 1, -1
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                if (!dfs(graph, color, i, 1)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean dfs(Map<Integer, List<Integer>> graph, int[] color, int currNode, int wantedColor) {
        if (color[currNode] != 0) {
            return color[currNode] == wantedColor;
        }
        color[currNode] = wantedColor;

        if (graph.containsKey(currNode)) {
            for (int next : graph.get(currNode)) {
                if (!dfs(graph, color, next, wantedColor*(-1))) {
                    return false;
                }
            }
        }
        return true;
    }

    private Map<Integer, List<Integer>> buildGraph(int[][] dislikes) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] dislike : dislikes) {
            graph.putIfAbsent(dislike[0], new ArrayList<>());
            graph.get(dislike[0]).add(dislike[1]);

            graph.putIfAbsent(dislike[1], new ArrayList<>());
            graph.get(dislike[1]).add(dislike[0]);
        }
        return graph;
    }
}


```
````