用Python编程将人员分开，没有敌人可以留在同一组中

pythonserver side programmingprogramming更新于 2026/2/3 21:32:17

假设我们有一个数字 n 和一个称为敌人的二维矩阵。这里n表示有n个人被标记为[0, n - 1]。现在敌人中的每一行都包含[a, b]，这意味着a和b是敌人。我们必须检查是否有可能将 n 个人分成两组，使得没有两个敌人属于同一组。

因此，如果输入为 n = 4，敌人 = [[0, 3],[3, 2]]，则输出将为 True，因为我们可以有这两个组 [0, 1, 2] 和 [3]。

为了解决这个问题，我们将遵循以下步骤 −

graph := 一个空的邻接列表
对于敌人中的每个敌人对 (u, v)，执行
- 在 graph[u] 的末尾插入 v
- 在 graph[v] 的末尾插入 u
color := 一个新的map
定义一个函数 dfs() 。这将首先采用 u, c := 0
如果 u 是 color，则
- 当 color[u] 与 c 相同时返回 true
color[u] := c
当 graph[u] 中每个 v 的所有 dfs(v, c XOR 1) 为 true 时返回 true
从主方法执行以下操作 −
当所有 (0 到 n 范围内的每个 u 的 dfs(u) 并且如果 u 不是 color) 为 true 时返回 true

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, n, enemies):
      from collections import defaultdict
      graph = defaultdict(list)
      for u, v in enemies:
         graph[u].append(v)
         graph[v].append(u)
      color = {}
      def dfs(u, c=0):
         if u in color:
            return color[u] == c
            color[u] = c
            return all(dfs(v, c ^ 1) for v in graph[u])
         return all(dfs(u) for u in range(n) if u not in color)
ob = Solution()
n = 4
enemies = [[0, 3],[3, 2]]
print(ob.solve(n, enemies))