# Possible Bipartition
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/possible-bipartition)
Canonical: https://scaleengineer.com/dsa/problems/possible-bipartition
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [Coupang](https://scaleengineer.com/companies/coupang), [Pinterest](https://scaleengineer.com/companies/pinterest), [Arcesium](https://scaleengineer.com/companies/arcesium), [Waymo](https://scaleengineer.com/companies/waymo)
---
## Problem
We want to split a group of `n` people (labeled from `1` to `n`) into two groups of **any size**. Each person may dislike some other people, and they should not go into the same group.

Given the integer `n` and the array `dislikes` where `dislikes[i] = [ai, bi]` indicates that the person labeled `ai` does not like the person labeled `bi`, return `true` _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:** The first group has [1,4], and the second group has [2,3].

**Example 2:**

**Input:** n = 3, dislikes = [[1,2],[1,3],[2,3]]
**Output:** false
**Explanation:** We need at least 3 groups to divide them. We cannot put them in two groups.

**Constraints:**

* `1 <= n <= 2000`
* `0 <= dislikes.length <= 104`
* `dislikes[i].length == 2`
* `1 <= ai < bi <= n`
* All the pairs of `dislikes` are **unique**.

# Approaches
## Brute-Force with Backtracking
This approach exhaustively explores all possible ways to partition the `n` people into two groups. It uses a recursive backtracking algorithm to try every possible assignment of a person to a group, pruning branches that lead to immediate conflicts.
**Time:** O(2^n * n). In the worst case, we explore a significant portion of the 2^n possible assignments. For each assignment step, we may check up to n-1 neighbors. · **Space:** O(n + E) to store the adjacency list and O(n) for the recursion stack depth. `E` is the number of dislikes.
**Pros:** Conceptually simple, directly modeling the problem of trying all possibilities.
**Cons:** Extremely inefficient with exponential time complexity, making it infeasible for the given constraints.; Does not handle disconnected components in a graph-native way.
### Explanation
We define a recursive function that attempts to assign a group to each person, one by one, from 1 to `n`. For each person, we try placing them in group 1. If this placement doesn't conflict with any previously assigned disliked neighbors, we proceed recursively to the next person. If the recursive path fails, we backtrack and try placing the person in group 2. A solution is found if we can successfully assign a group to all `n` people. This method is conceptually straightforward but computationally expensive, as it may need to explore a number of possibilities that is exponential in `n`.\n\n```java\nclass Solution {\n    public boolean possibleBipartition(int n, int[][] dislikes) {\n        List<Integer>[] adj = new ArrayList[n + 1];\n        for (int i = 1; i <= n; i++) {\n            adj[i] = new ArrayList<>();\n        }\n        for (int[] d : dislikes) {\n            adj[d[0]].add(d[1]);\n            adj[d[1]].add(d[0]);\n        }\n        int[] groups = new int[n + 1]; // 0: unassigned, 1: group A, 2: group B\n        return solve(1, n, adj, groups);\n    }\n\n    private boolean solve(int personId, int n, List<Integer>[] adj, int[] groups) {\n        if (personId > n) {\n            return true;\n        }\n\n        // Try assigning to group 1\n        if (isValid(personId, 1, adj, groups)) {\n            groups[personId] = 1;\n            if (solve(personId + 1, n, adj, groups)) {\n                return true;\n            }\n        }\n\n        // Try assigning to group 2\n        if (isValid(personId, 2, adj, groups)) {\n            groups[personId] = 2;\n            if (solve(personId + 1, n, adj, groups)) {\n                return true;\n            }\n        }\n        \n        groups[personId] = 0; // Backtrack\n        return false;\n    }\n\n    private boolean isValid(int personId, int group, List<Integer>[] adj, int[] groups) {\n        for (int neighbor : adj[personId]) {\n            if (groups[neighbor] == group) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```
### Algorithm
- Create an adjacency list to represent the dislike relationships for quick lookups.\n- Create a `groups` array to store the group assignment for each person (e.g., 1 for group A, 2 for group B).\n- Define a recursive function `solve(personId)` that tries to assign a group to `personId`.\n- Base Case: If `personId` is greater than `n`, it means all people have been successfully assigned, so return `true`.\n- Recursive Step:\n  - Try assigning `personId` to group 1. Check if this conflicts with any neighbors of `personId` that are already in group 1.\n  - If it's a valid move, recursively call `solve(personId + 1)`. If the call returns `true`, a solution is found, so propagate `true`.\n  - If not, try assigning `personId` to group 2, performing a similar check and recursive call.\n  - If neither assignment leads to a solution, backtrack by returning `false`.

## Graph Coloring using Depth-First Search (DFS)
This problem can be reframed as a graph coloring problem. We can represent the people as vertices and the dislike relationships as edges in a graph. The question then becomes: is this graph bipartite? A graph is bipartite if we can color its vertices with two colors such that no two adjacent vertices have the same color. DFS is a classic and efficient algorithm for this task.
**Time:** O(n + E), where `n` is the number of people and `E` is `dislikes.length`. We visit each vertex and edge once. · **Space:** O(n + E) for the adjacency list, `colors` array, and recursion stack.
**Pros:** Highly efficient with linear time complexity.; Correctly handles disconnected graphs.; Standard and robust algorithm for bipartiteness checking.
**Cons:** Requires understanding of graph theory and DFS.; Recursive implementation could theoretically cause a stack overflow on extremely deep graphs, though unlikely with given constraints.
### Explanation
We first build an adjacency list to represent the graph. We also use a `colors` array to store the color of each vertex (person), with possible states like uncolored, color A, or color B. We iterate through all people to handle graphs that may have multiple disconnected components. If a person is uncolored, we start a DFS traversal from them. During the DFS, we color the current vertex and then visit its neighbors. If a neighbor is uncolored, we recursively call DFS on it with the opposite color. If a neighbor is already colored and has the same color as the current vertex, we have detected an odd-length cycle, which means the graph is not bipartite, and we return `false`. If all components can be two-colored without conflict, we return `true`.\n\n```java\nclass Solution {\n    public boolean possibleBipartition(int n, int[][] dislikes) {\n        List<Integer>[] adj = new ArrayList[n + 1];\n        for (int i = 1; i <= n; i++) {\n            adj[i] = new ArrayList<>();\n        }\n        for (int[] d : dislikes) {\n            adj[d[0]].add(d[1]);\n            adj[d[1]].add(d[0]);\n        }\n\n        int[] colors = new int[n + 1]; // 0: uncolored, 1: color A, -1: color B\n        for (int i = 1; i <= n; i++) {\n            if (colors[i] == 0) {\n                if (!dfs(i, 1, colors, adj)) {\n                    return false;\n                }\n            }\n        }\n        return true;\n    }\n\n    private boolean dfs(int node, int color, int[] colors, List<Integer>[] adj) {\n        colors[node] = color;\n        for (int neighbor : adj[node]) {\n            if (colors[neighbor] == 0) {\n                if (!dfs(neighbor, -color, colors, adj)) {\n                    return false;\n                }\n            } else if (colors[neighbor] == color) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```
### Algorithm
- Build an adjacency list `adj` from the `dislikes` array.\n- Initialize a `colors` array (size `n+1`) with a value indicating 'uncolored' (e.g., 0).\n- Iterate from `i = 1` to `n`:\n  - If person `i` is uncolored (`colors[i] == 0`):\n    - Start a DFS from `i` by calling a helper function `dfs(i, 1)`, attempting to color `i` with the first color.\n    - If `dfs` returns `false`, a conflict was found, so the partition is impossible. Return `false`.\n- If the loop completes, return `true`.\n- **DFS helper `dfs(node, color)`:**\n  - Color the `node` with the given `color`.\n  - For each `neighbor` of `node`:\n    - If `neighbor` is uncolored, recursively call `dfs(neighbor, -color)`. If this call returns `false`, propagate `false`.\n    - If `neighbor` has the same color as `node`, return `false`.\n  - Return `true` if no conflicts are found for this `node`.

## Graph Coloring using Breadth-First Search (BFS)
This is another optimal approach that treats the problem as checking for graph bipartiteness. It uses Breadth-First Search (BFS) instead of DFS. BFS explores the graph layer by layer, which is also perfectly suited for two-coloring.
**Time:** O(n + E), where `n` is the number of people and `E` is `dislikes.length`. Each vertex and edge is processed once. · **Space:** O(n + E) for the adjacency list, `colors` array, and the queue. The queue can hold up to O(n) vertices in the worst case.
**Pros:** Optimal linear time complexity, same as DFS.; Iterative approach avoids any risk of stack overflow errors.; Also correctly handles disconnected graphs.
**Cons:** Requires understanding of graph theory and BFS.; The code can be slightly more verbose than the recursive DFS version.
### Explanation
Like the DFS approach, we start by building an adjacency list and a `colors` array. We iterate through all people to ensure all connected components are checked. For each uncolored person, we initiate a BFS. We add the person to a queue and assign them an initial color. Then, we enter a loop that continues as long as the queue is not empty. In each iteration, we dequeue a person `u` and examine their neighbors. If a neighbor `v` is uncolored, we assign it the opposite color of `u` and enqueue it. If `v` is already colored and has the same color as `u`, a conflict is found, and we immediately know a valid partition is impossible.\n\n```java\nclass Solution {\n    public boolean possibleBipartition(int n, int[][] dislikes) {\n        List<Integer>[] adj = new ArrayList[n + 1];\n        for (int i = 1; i <= n; i++) {\n            adj[i] = new ArrayList<>();\n        }\n        for (int[] d : dislikes) {\n            adj[d[0]].add(d[1]);\n            adj[d[1]].add(d[0]);\n        }\n\n        int[] colors = new int[n + 1]; // 0: uncolored, 1: color A, -1: color B\n        Queue<Integer> queue = new LinkedList<>();\n\n        for (int i = 1; i <= n; i++) {\n            if (colors[i] == 0) {\n                queue.offer(i);\n                colors[i] = 1;\n                while (!queue.isEmpty()) {\n                    int u = queue.poll();\n                    for (int v : adj[u]) {\n                        if (colors[v] == 0) {\n                            colors[v] = -colors[u];\n                            queue.offer(v);\n                        } else if (colors[v] == colors[u]) {\n                            return false;\n                        }\n                    }\n                }\n            }\n        }\n        return true;\n    }\n}\n```
### Algorithm
- Build an adjacency list `adj` from the `dislikes` array.\n- Initialize a `colors` array (size `n+1`) with a value indicating 'uncolored' (e.g., 0).\n- Iterate from `i = 1` to `n`:\n  - If person `i` is uncolored (`colors[i] == 0`):\n    - Create a queue, add `i` to it, and color `i` with the first color (`colors[i] = 1`).\n    - While the queue is not empty:\n      - Dequeue a person `u`.\n      - For each `neighbor` `v` of `u`:\n        - If `v` is uncolored, color it with the opposite color (`-colors[u]`) and enqueue it.\n        - If `v` has the same color as `u`, return `false`.\n- If the loop completes without returning `false`, return `true`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  boolean possibleBipartition(int n, int[][] dislikes) {
    p = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (var e : dislikes) {
      int a = e[0] - 1, b = e[1] - 1;
      g[a].add(b);
      g[b].add(a);
    }
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        if (find(i) == find(j)) {
          return false;
        }
        p[find(j)] = find(g[i].get(0));
      }
    }
    return true;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool possibleBipartition(int n, vector<vector<int>> &dislikes) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    unordered_map<int, vector<int>> g;
    for (auto &e : dislikes) {
      int a = e[0] - 1, b = e[1] - 1;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x)
        p[x] = find(p[x]);
      return p[x];
    };
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        if (find(i) == find(j))
          return false;
        p[find(j)] = find(g[i][0]);
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] g = defaultdict(list) for a, b in dislikes: a, b = a - 1, b - 1 g[a]. append(b) g[b]. append(a) p = list(range(n)) for i in range(n): for j in g[i]: if find(i) == find(j): return False p[find(j)] = find(g[i][0]) return True

```