886.Possible Bipartition

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

題目描述

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⁴
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

KobeDec 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;
    }
};

Yen-Chi ChenWed, 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;
}

MarsgoatDec 21, 2022

Reference

回到題目列表