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

# Possible Bipartition

Given a set of `N` people (numbered `1, 2, ..., N`), we would like to split everyone into two groups of **any** size.

Each person may dislike some other people, and they should not go into the same group. 

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

Return `true` if and only if it is possible to split everyone into two groups in this way.

1.

**Example 1:**

```
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]
```

**Example 2:**

```
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
```

**Example 3:**

```
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
```

**Constraints:**

* `1 <= N <= 2000`
* `0 <= dislikes.length <= 10000`
* `dislikes[i].length == 2`
* `1 <= dislikes[i][j] <= N`
* `dislikes[i][0] < dislikes[i][1]`
* There does not exist `i != j` for which `dislikes[i] == dislikes[j]`.

```java
class Solution {
    // Color -> 0 not colored YET
    // Color -> 1 (one of the colors)
    // Color -> -1 (The other color)
    // colors array works as color storage as well as visited array
    int[] colors;
    List<Integer>[] graph;

    public boolean possibleBipartition(int N, int[][] dislikes) {
        // Creating adjacency list graph
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++)
            graph[i] = new ArrayList<>();
        for (int[] pair : dislikes) {
            graph[pair[0] - 1].add(pair[1] - 1);
            graph[pair[1] - 1].add(pair[0] - 1);
        }
        colors = new int[N];
        for (int i = 0; i < N; i++)
            if (colors[i] == 0 && !paint(i, 1))
                return false;
        return true;
    }

    boolean paint(int u, int color) {
        // "color" -> the color we want this person ("u") to be
        if (colors[u] != 0)
            return colors[u] == color;
        colors[u] = color;
        for (int neighbor : graph[u])
            // If we cannot paint the neighbor with opposite color
            if (!paint(neighbor, -color))
                return false;
        return true;
    }
}
```