有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

示例 1：

输入：N = 3, paths = [[1,2],[2,3],[3,1]]

输出：[1,2,3]

示例 2：

输入：N = 4, paths = [[1,2],[3,4]]

输出：[1,2,1,2]

示例 3：

输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]

输出：[1,2,3,4]

1 <= N <= 10000
0 <= paths.size <= 20000

不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。

在python中可以使用列表作为队列,list用append添加元素

可以用字典来存储邻接节点nei = {}

在集合中使用for循环

{res[j] for j in G[i]}

集合的pop函数

flowers = {1,2,3,4} #集合直接相减即可
flowers.pop()
# 集合不能获取某个元素这样子的操作
print(flowers)

out: {2,3,4}集合中的pop是从左边开始取

集合的相减

flowers = {1,2,3,4}
h = {0}
flowers-h

out:{1,2,3,4}
class Solution: # 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一 def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: #构建一个answer数组 answer = [0 for _ in range(N)] #构建所有节点 all_nodes = [] [all_nodes.append(i) for i in range(1,N+1)] #构建visted列表 visted = dict.fromkeys(all_nodes, 0) #初始化nei字典元素为空列表 nei = [[] for _ in range(N)] # 构建无向邻接表，无邻居则不构建 for path in paths: nei[path[0]-1].append(path[1]) nei[path[1]-1].append(path[0]) #遍历每一个点，每个点保证自己邻接点不是和自己相同就行 answer[0] = 1 for node in range(1,N+1): #遍历所有节点 visted[node] = 1 fix = set() if(answer[node-1]==0): #如果为0,说明不是连通图 answer[node-1] = 1 flowers=[1,2,3,4] nei[node-1] = sorted(nei[node-1]) #排序邻居节点 flowers.pop(answer[node-1]-1) #弹出父节点的flowers for sinode in nei[node-1]: #遍历邻居 if(visted[sinode] == 0): #如果邻居未被访问过 answer[sinode-1] = flowers[0] #使用1,弹出1 flowers.pop(0) else: #如果邻居被访问过 if(answer[sinode-1]==answer[node-1]): answer[node-1] = flowers[0] flowers.pop(0) fix.add(answer[sinode-1]) if not fix: continue else: flowers=[1,2,3,4] for a_val in list(fix): flowers.remove(a_val) answer[node-1] = flowers[0] return answer

简化方法:利用集合快速搞定

class Solution: def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: #构建一个answer数组 answer = [0]*N #初始化nei字典元素为空列表 nei = [[] for _ in range(N)] # 构建无向邻接表，无邻居则不构建 for path in paths: nei[path[0]-1].append(path[1]) nei[path[1]-1].append(path[0]) for node in range(1,N+1): #遍历所有节点 flowers={1,2,3,4} #临时存储邻居含有的花类型 a = set() for sinode in nei[node-1]: #遍历邻居 a.add(answer[sinode-1]) flowers = flowers - a answer[node-1] = flowers.pop() return answer

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

您可能感兴趣的文章:

• python实现邻接表转邻接矩阵
• Python数据结构之图的存储结构详解
• Python如何自定义邻接表图类

• 

  python实现RSA加密(解密)算法

  RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准，下面通过本文给大家介绍python实现RSA加密(解密)算法，需要的朋友参考下

  2016-02-02
• 

  Pygame Display显示模块的使用方法

  本文主要介绍了Pygame Display显示模块的使用方法，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

  2021-11-11
• 

  Django的多表查询操作实战

  Django提供一种强大而又直观的方式来"处理"查询中的关联关系,它在后台自动帮你处理JOIN,下面这篇文章主要给大家介绍了关于Django多表查询操作的相关资料,文中通过实例代码介绍的非常详细,需要的朋友可以参考下

  2023-06-06
• 

  Python初学者必备的文件读写指南

  今天给大家带来的是关于Python基础的相关知识,文章围绕着Python文件读写展开,文中有非常详细的介绍及代码示例,需要的朋友可以参考下

  2021-06-06
• 

  python实现提取str字符串/json中多级目录下的某个值

  今天小编就为大家分享一篇python实现提取str字符串/json中多级目录下的某个值，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧

  2020-02-02
• 

  python django 增删改查操作 数据库Mysql

  下面小编就为大家带来一篇python django 增删改查操作 数据库Mysql。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧

  2017-07-07
• 

  Python基础之函数基本用法与进阶详解

  这篇文章主要介绍了Python基础之函数基本用法与进阶,结合实例形式总结分析了Python函数的定义、参数、返回值及递归等相关使用技巧与操作注意事项,需要的朋友可以参考下

  2020-01-01
• 

  Python+Pygame实战之文字剧情游戏的实现

  这篇文章主要为大家详细介绍了如何利用Python和Pygame实现两款文字剧情游戏——《巨龙之洞》和《太空矿工》，感兴趣的小伙伴可以了解一下

  2022-12-12
• 

  python上下文管理的使用场景实例讲解

  在本篇文章里小编给大家整理的是一篇关于python上下文管理的使用场景实例讲解内容，有兴趣的朋友们可以学习下。

  2021-03-03
• 

  Python基础之函数原理与应用实例详解

  这篇文章主要介绍了Python基础之函数原理与应用,结合具体实例形式详细分析了Python函数的定义、原理、参数、返回值、嵌套等相关概念与使用技巧,需要的朋友可以参考下

  2020-01-01