> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/breadth-first-search/886-possible-bipartition.md).

# 886 Possible Bipartition

## 886. [Possible Bipartition](https://leetcode.com/problems/possible-bipartition/description/)

## 1. Question

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.

**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
```

**Note:**

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

## 2. Implementation

思路: 用BFS对图进行染色，如果相邻的点是不同颜色，则可以分成二分图

```java
class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] colors = new int[N + 1];
        Arrays.fill(colors, -1);

        List<Set<Integer>> adjList = new ArrayList();

        for (int i = 0; i <= N; i++) {
            adjList.add(new HashSet());
        }

        for (int[] dislike : dislikes) {
            adjList.get(dislike[0]).add(dislike[1]);
            adjList.get(dislike[1]).add(dislike[0]);
        }

        Queue<Integer> queue = new LinkedList();


        for (int i = 1; i <= N; i++) {
            if (colors[i] == -1) {
                colors[i] = 1;
                queue.add(i);

                while (!queue.isEmpty()) {
                    int curNode = queue.remove();

                    for (int nextNode : adjList.get(curNode)) {
                        if (colors[nextNode] == -1) {
                            colors[nextNode] = 1 - colors[curNode];
                            queue.add(nextNode);
                        }
                        else if (colors[nextNode] == colors[curNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}
```

## 3. Time  & Space Complexity

时间复杂度O(n), 空间复杂度O(n)