Python程序：将人员分组，确保无敌人处于同一组

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

因此，如果输入类似于n = 4，enemies = [[0, 3],[3, 2]]，则输出为True，因为我们可以有这两组[0, 1, 2]和[3]。

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

  • graph := 一个空的邻接表

  • 对于enemies中的每个敌人对(u, v)，执行以下操作：

    • 将v插入graph[u]的末尾

    • 将u插入graph[v]的末尾

  • color := 一个新的映射

  • 定义一个函数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，如果u不在color中，则dfs(u))都为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))

输入

4, [[0, 3],[3, 2]]

输出

True

更新于：2020年10月21日

522 次浏览

启动你的职业生涯

完成课程后获得认证

开始
广告