难度：★★★☆☆
类型：图
方法：贪心
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。
另外，所有花园 最多 有 3 条路径可以进入或离开.
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
示例 1：
输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]
示例 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 <= 104
0 <= paths.length <= 2 * 104
paths[i].length == 2
1 <= xi, yi <= n
xi != yi
每个花园 最多 有 3 条路径可以进入或离开
解答
我们把花园看成结点，联系各个结点的路径用数组集合的方式给出，很容易想到用深度优先搜索或宽度优先搜索的方法探索连通域。
解法1：深度优先搜索
第一步，建图。
为了便于表达，我们把用字典的形式存储每个结点的临近结点。这里需要注意的是，为了便于python索引，我们把每个花园编号减1，将1到n范围转到了0到n-1范围。graph[node]是一个列表，里面是与node结点相邻的所有结点。
第二步，染色列表。
为了存储每个花园的染色结果，我们准备一个列表color_of_，color_of_[node]表示node结点被染色的结果，列表长度为n，默认值为0，每个位置将要被染色成1,2,3,4中的一个。
第三步，深度优先搜索。
定义深度优先搜索函数实现循环染色。函数有两个输入，一个是结点node，一个是该结点需要被染色的结果color，函数返回值是布尔量，表达能否成功染色。函数过程中执行染色操作。
入口处需要优先判断是否能被染色，遍历node的每个相邻结点，如果发现任何一个相邻结点已经被染色为color，则染色失败，直接返回False。
如果通过了上面的校验，则可以将该结点染色，color_of_[node] = color，接下来就是把node的临近结点neighbor染色，这里需要注意颜色的选择。我们需要选择除了color以外的所有颜色，将这些颜色分别做尝试，一旦尝试成功，则不再进行其他颜色的尝试。临近结点neighbor的选择也有讲究，如果该节点已经被染了色，也就是该节点处color_of_对应位置处的值不是零，该节点是不需要再考虑的。如果所有临近结点都完成染色，则dfs返回值记得设置为True，代表node结点染色成功。
第四步，遍历。
接下来就是使用dfs函数的时候。我们有必要遍历每一个结点，一旦某结点没有被染色（通过color_of_[node] 是否为零判断），则调用dfs函数进行染色，颜色的选择与上面类似，需要进行尝试。
题目的解答过程实际上就是color_of_的填充过程，所有结点遍历完成后，如果发现color_of_中还有没有被染色的结点，也就是0 in color_of_，则说明无法完成所有结点的染色，否则，直接返回染色结果。
编程中其他注意事项：
第一，为了给字典提供默认值，我们使用defaultdict类；
第二，dfs函数的设计过程中，需要将终止条件写在开头。
from collections import defaultdict
class Solution:
def gardenNoAdj(self, n, paths):
graph = defaultdict(set)
for u, v in paths:
u, v = u - 1, v - 1
graph[u].add(v)
graph[v].add(u)
color_of_ = [0] * n
colors = {1, 2, 3, 4}
def dfs(node, color):
for neighbor in graph[node]:
if color_of_[neighbor] == color:
return False
color_of_[node] = color
for color in colors - {color}:
for neighbor in graph[node]:
if color_of_[neighbor] == 0 and dfs(neighbor, color):
return True
return True
for node in range(n):
if color_of_[node] == 0:
for color in colors:
if dfs(node, color):
break
if 0 in color_of_:
return "Unable for color!"
return color_of_
s = Solution()
print(s.gardenNoAdj(3, [[1,2],[2,3],[3,1]]))
print(s.gardenNoAdj(4, [[1,2],[3,4]]))
print(s.gardenNoAdj(4, [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]))
print(s.gardenNoAdj(5, [[1, 2], [1, 3], [1, 4], [1, 5],
[2, 3], [2, 4], [2, 5],
[3, 4], [3, 5],
[4, 5],
]))
解法2：贪心
因为题目已经告诉了我们，染色是一定可以成功的，我们就可以直接放心的填充每一个结点了。最关键的填充什么颜色。对于某一个结点node，其颜色需要根据临近结点填充，而且有的临近结点已经被填充过了，有的没有，我们只需要考虑被填充过的那些就好，需要保证该结点的颜色与那些已经被填充过的结点颜色都不同，至于到底填什么颜色，随便弹出一个满足条件的就够了。只要每填充一个结点，都按照上面的法则，则填充结果一定是满足要求的。这样在写法上是非常简单的。
python里通过集合相减的操作实现剩余颜色的获取。
from collections import defaultdict
from typing import List
class Solution:
def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
graph = defaultdict(list)
for u, v in paths:
u, v = u - 1, v - 1
graph[u].append(v)
graph[v].append(u)
ans = [0] * n
for u in range(n):
colors = {1, 2, 3, 4} - set(ans[v] for v in graph[u])
ans[u] = colors.pop()
return ans
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
