886.Possible Bipartition
===

###### tags: `Medium`,`DFS`,`BFS`,`Graph`

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

### 題目描述

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]` = [$a_i$, $b_i$] indicates that the person labeled $a_i$ does not like the person labeled $b_i$, 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: group1 [1,4] and 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` <= 10^4^
* `dislikes[i].length` == 2
* 1 <= `dislikes[i][j]` <= `n`
* $a_i$ < $b_i$
* All the pairs of `dislikes` are **unique**.

### 解答
#### Python

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(dict)
        color = [-1] * (n + 1)

        for u, v in dislikes:
            graph[u][v] = 1
            graph[v][u] = 1

        def dfs(node, node_color):
            color[node] = node_color
            
            for nei in graph[node].keys():
                # 相鄰需不同色
                if color[nei] == color[node]: 
                    return False
                if color[nei] == -1:
                    if not dfs(nei, 1 - node_color):
                        return False

            return True

        for i in range(1, n + 1):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False

        return True

>[name=Kobe][time=Dec 21, 2022]

#### C++

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<int> adj[n+1];
        for (auto dislike : dislikes) {
            adj[dislike[0]].push_back(dislike[1]);
            adj[dislike[1]].push_back(dislike[0]);
        }
        vector<int> colors(n+1, 0);
        function<bool(int, int)> dfs = [&](int cur, int color) {
            if (colors[cur] != 0) return colors[cur] == color;
            colors[cur] = color;
            for (auto next : adj[cur]) {
                if (!dfs(next, -color)) return false;
            }
            return true;
        };
        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0 && !dfs(i, 1)) return false;
        }
        return true;
    }
};

> [name=Yen-Chi Chen][time=Wed, Dec 21, 2022]

#### Javascirpt

function possibleBipartition(n, dislikes) {
  const graph = [];
  for (const [v1, v2] of dislikes) {
    if (graph[v1] === undefined) graph[v1] = [];
    if (graph[v2] === undefined) graph[v2] = [];
    graph[v1].push(v2);
    graph[v2].push(v1);
  }

  const color = new Array(n + 1).fill(0);
  const stack = [];

  for (let i = 1; i <= n; i++) {
    if (color[i] !== 0) continue;
    stack.push(i);

    // 做DFS 依序塗色跟檢查
    while (stack.length) {
      const node = stack.pop();
      if (color[node] === 0) {
        color[node] = 1;
      }

      if (graph[node] === undefined) continue; // 與所有點都不相連

      // 相鄰的點要跟自己不同色
      for (const vertex of graph[node]) {
        if (color[vertex] === 0) {
          color[vertex] = -color[node];
          stack.push(vertex);
        } else if (color[vertex] === color[node]) {
          return false;
        }
      }
    }
  }

  return true;
}

>[name=Marsgoat][time=Dec 21, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)