数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 次浏览
广告