886_可能的二分法

类型：图

• 886. 可能的二分法 💛

  https://leetcode-cn.com/problems/possible-bipartition/

  ❓ 给定一组 N 人（编号为 1, 2, …, N），将他们分成两个小组。互相讨厌的人不能放到同一组。数组 dislikes 中，dislikes[i] = [a, b] 表示 a、b 两人互相讨厌。问是否能够顺利完成分组。

  输入：N = 4, dislikes = 1,2 输出：true 解释：group1 [1,4], group2 [2,3]

  💡 涂色法

  这一题其实跟「785. 判断二分图」是一样的，区别在于 785 题中是用邻接数组表示边，而此题是用边集数组表示边。

  # 我的实现
  class Solution:
      def __init__(self):
          self.graph = []
          self.colors = []
  
      def dfs(self, i, color):
          # 如果涂色出现冲突
          if any(self.colors[k] == color for k in self.graph[i]):
              return False
          # 涂色
          self.colors[i] = color
          # 继续给邻接点涂色
          for k in self.graph[i]:
              if self.colors[k] == 0:
                  if not self.dfs(k, color * -1):
                      return False
          return True
  
      def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
          self.colors = [0] * (N + 1)
          # 将边集数组转换成邻接表
          self.graph = [[] for _ in range(N + 1)]
          for edge in dislikes:
              if not edge[1] in self.graph[edge[0]]:
                  self.graph[edge[0]].append(edge[1])
              if not edge[0] in self.graph[edge[1]]:
                  self.graph[edge[1]].append(edge[0])
  
          for i in range(1, N+1):
              if self.colors[i] == 0:
                  if not self.dfs(i, 1):
                      return False
          return True

  class Solution(object):
      def possibleBipartition(self, N, dislikes):
          graph = collections.defaultdict(list)
          for u, v in dislikes:
              graph[u].append(v)
              graph[v].append(u)
  
          color = {}
          def dfs(node, c = 0):
              if node in color:
                  return color[node] == c
              color[node] = c
              return all(dfs(nei, c ^ 1) for nei in graph[node])
  
          return all(dfs(node)
                     for node in range(1, N+1)
                     if node not in color)

  时间复杂度：O(N + E)，N 为结点数，E 为dislikes 长度。空间复杂度：O(N + E)