# LeetCode 886: Possible Bipartition

## Problem Restatement

We are given `n` people labeled from `1` to `n`.

We are also given a list `dislikes`, where each pair:

```text
[a, b]
```

means person `a` dislikes person `b`, and person `b` dislikes person `a`.

We need to split everyone into two groups so that no pair of people who dislike each other are in the same group.

Return `true` if this is possible. Otherwise, return `false`.

This is exactly a bipartite graph problem: people are nodes, dislikes are edges, and we need to color the graph with two colors so that every edge connects nodes of different colors. The official constraints allow `n <= 2000` and up to `10^4` dislike pairs.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, the number of people |
| Input | `dislikes`, a list of dislike pairs |
| Output | `true` if a valid split exists, otherwise `false` |
| Person labels | `1` through `n` |
| Relationship | Undirected |
| Group count | Exactly two groups are allowed |

Function shape:

```python
def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
```

One valid split is:

| Group | People |
|---|---|
| Group 1 | `1, 4` |
| Group 2 | `2, 3` |

Check every dislike pair:

| Pair | Same group? |
|---|---|
| `[1,2]` | No |
| `[1,3]` | No |
| `[2,4]` | No |

So the answer is `true`.

Example 2:

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

This forms a triangle:

```text
1 dislikes 2
1 dislikes 3
2 dislikes 3
```

With only two groups, two of these people must share a group. But every pair dislikes each other, so this is impossible.

## First Thought: Try Assigning Groups Recursively

A direct idea is to try all possible assignments of people to two groups.

Each person can go into group `A` or group `B`.

For `n` people, that gives:

```text
2^n
```

possible assignments.

For each assignment, we could check whether any dislike pair is inside the same group.

This is correct, but much too slow for `n <= 2000`.

We need to use the structure of the dislike relationships.

## Key Insight

Think of the problem as a graph.

| Problem object | Graph object |
|---|---|
| Person | Node |
| Dislike pair | Undirected edge |
| Group | Color |

We need to color every node using two colors.

For every edge `[a, b]`, nodes `a` and `b` must have different colors.

So the question becomes:

```text
Is the graph bipartite?
```

A graph is bipartite if its nodes can be divided into two sets so that every edge goes between the two sets.

We can test this using DFS or BFS.

## Algorithm

Build an adjacency list.

For each dislike pair `[a, b]`:

```python
graph[a].append(b)
graph[b].append(a)
```

Use an array `color`.

| Value | Meaning |
|---|---|
| `0` | Uncolored |
| `1` | First group |
| `-1` | Second group |

Then scan all people from `1` to `n`.

If a person is uncolored, start a DFS or BFS from that person and assign color `1`.

For each edge from `person` to `neighbor`:

1. If `neighbor` is uncolored, color it with the opposite color.
2. If `neighbor` already has the same color as `person`, return `false`.

If all connected components are colored successfully, return `true`.

We must scan all people because the graph may be disconnected.

## Walkthrough

Use:

```text
n = 4
dislikes = [[1,2],[1,3],[2,4]]
```

Build the graph:

| Person | Dislikes |
|---|---|
| `1` | `2, 3` |
| `2` | `1, 4` |
| `3` | `1` |
| `4` | `2` |

Start at person `1`.

Assign:

```text
color[1] = 1
```

Neighbors `2` and `3` must get the opposite color:

```text
color[2] = -1
color[3] = -1
```

From person `2`, neighbor `4` must get the opposite color:

```text
color[4] = 1
```

Final colors:

| Person | Color |
|---|---:|
| `1` | `1` |
| `2` | `-1` |
| `3` | `-1` |
| `4` | `1` |

Every dislike edge connects different colors, so the split is possible.

## Correctness

The algorithm assigns colors so that every dislike edge connects two people in different groups.

When the algorithm visits an edge from `person` to `neighbor`, there are two cases.

If `neighbor` has no color yet, the algorithm gives it the opposite color from `person`. This satisfies the edge constraint for that edge.

If `neighbor` already has a color, the algorithm checks whether it equals `color[person]`. If the colors are equal, then the two people would be in the same group despite disliking each other. No valid bipartition can keep this coloring and satisfy the edge, so the algorithm returns `false`.

If no conflict is found, every checked dislike edge connects different colors.

The algorithm starts a traversal from every uncolored person, so it covers all connected components, not only the component containing person `1`.

Therefore, if the algorithm returns `true`, every dislike pair has endpoints in different groups, so a valid bipartition exists.

If a valid bipartition exists, graph coloring with two colors is possible. The traversal only forces neighbors to have opposite colors, which is required by every valid bipartition. Since no odd-cycle conflict exists in a bipartite graph, the algorithm will never find two adjacent nodes with the same color. Therefore, it will return `true`.

Thus, the algorithm is correct.

## Complexity

Let:

```text
V = n
E = len(dislikes)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(V + E)` | We visit each person and each dislike edge |
| Space | `O(V + E)` | The graph stores all edges and the color array stores all people |

## Implementation

```python
from collections import deque

class Solution:
    def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
        graph = [[] for _ in range(n + 1)]

        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        color = [0] * (n + 1)

        for start in range(1, n + 1):
            if color[start] != 0:
                continue

            color[start] = 1
            queue = deque([start])

            while queue:
                person = queue.popleft()

                for neighbor in graph[person]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[person]
                        queue.append(neighbor)
                    elif color[neighbor] == color[person]:
                        return False

        return True
```

## Code Explanation

We create an adjacency list with `n + 1` slots:

```python
graph = [[] for _ in range(n + 1)]
```

The people are labeled from `1` to `n`, so index `0` is unused.

For each dislike pair, we add both directions:

```python
graph[a].append(b)
graph[b].append(a)
```

This is an undirected graph.

The color array starts with all people uncolored:

```python
color = [0] * (n + 1)
```

We scan all people:

```python
for start in range(1, n + 1):
```

If a person already has a color, that person belongs to a component we have already processed.

If not, we start a BFS:

```python
color[start] = 1
queue = deque([start])
```

For every neighbor, if it has no color, we assign the opposite color:

```python
color[neighbor] = -color[person]
```

If a neighbor already has the same color, the bipartition is impossible:

```python
elif color[neighbor] == color[person]:
    return False
```

If the BFS finishes for every component without conflict, we return:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.possibleBipartition(
        4,
        [[1, 2], [1, 3], [2, 4]]
    ) is True

    assert s.possibleBipartition(
        3,
        [[1, 2], [1, 3], [2, 3]]
    ) is False

    assert s.possibleBipartition(
        5,
        [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]]
    ) is False

    assert s.possibleBipartition(
        4,
        []
    ) is True

    assert s.possibleBipartition(
        6,
        [[1, 2], [3, 4], [5, 6]]
    ) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[1,2],[1,3],[2,4]]` | Standard valid split |
| Triangle conflict | Odd cycle cannot be bipartitioned |
| Five-node odd cycle | Larger conflict case |
| No dislikes | Everyone can be split arbitrarily |
| Disconnected components | Confirms all components are checked |