# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/breadth-first-search/886-possible-bipartition.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.