在Python中没有敌人可以呆在同一组中的人的程序

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

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

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

• 图：=一个空的邻接表

• 对于敌人中的每个敌人对(u,v)，执行

• 在图形的末尾插入v [u]

• 在图形[v]的末尾插入u

• 颜色：=新映射

• 定义一个函数dfs()。最初需要u，c：= 0

• 如果你是彩色的，那么

• 当color [u]与c相同时返回true

• 颜色[u]：= c

• 当graph [u]中每个v的所有dfs（v，c XOR 1）全部为true时，返回true

• 从主要方法中执行以下操作-

• 当所有（dfs(u)都在0到n范围内并且如果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