发表于 2024.05.21

• 这种与关系相关联的题目一般而言可以使用图来建模，本题目的厌恶关系可以使用无向图连接起来，然后使用染色法对节点进行染色：节点和其相邻的节点不能处在同一个颜色中。我们可以使用DFS递归染色：邻接节点的期望颜色和当前节点的颜色相反，如果邻接节点已经染色且和当前节点处在同一个颜色，则无法进行二分，不满足题意。

  class Solution:
      def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
          adj_list = [[] for _ in range(n + 1)]
          for u, v in dislikes:
              adj_list[u].append(v)
              adj_list[v].append(u)
  
          group = [-1] * (n + 1)
  
          def dfs(node: int, desired_group: int):
              if group[node] != -1:
                  if group[node] != desired_group:
                      return False
                  return True
              group[node] = desired_group
  
              for next_ in adj_list[node]:
                  if not dfs(next_, 1 - desired_group):
                      return False
              return True
  
          for i in range(1, n + 1):
              if group[i] == -1:
                  if not dfs(i, 0):
                      return False
          return True

  一开始不正确的做法，主要问题出在如果两人之前都没有标记过，则默认将第一个人(设为x)标记在组0内，但后面可能会有这种情况：组0的某个人y会连接同为组0的x，而x分在组1内是可以的：

  class Solution:
      def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
          group = [-1] * (n + 1)
          for u, v in dislikes:
              if group[u] == group[v] != -1:
                  return False
              if group[u] != -1:
                  group[v] = 1 - group[u]
              elif group[v] != -1:
                  group[u] = 1 - group[v]
              else:  # all -1
                  group[u] = 0
                  group[v] = 1
          return True

  错误的样例：

  [[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]

• LC 题目链接