题目描述
思路解析
一句话答案：LeetCode 1042 不邻接植花：每个花园最多 3 个邻居、却有 4 种花可选，按编号逐个花园挑一个邻居没占的花色，3 比 4 小保证永远挑得到，一趟贪心染色搞定，时间 O(n+m)。
n 个花园要种花，种法得满足什么
n 个花园编号 1 到 n，paths 里每个 [x, y] 表示花园 x、y 间有双向小路、算相邻。有 4 种花（1、2、3、4），给每园种一种、让相连花园花色不同，返回 answer，answer[i] 是第 i+1 个花园的花色。题目保证每园最多 3 条小路、且有解。
题面例子 n=3、paths=[[1,2],[2,3],[3,1]]，三个花园围成三角、两两相连，输出 [1,2,3]。
一般的图染色为什么这么费劲
给点涂色、让相邻两点颜色不同，这类问题叫图染色。判断一张图能不能用 k 种颜色染完是出了名的难题，最坏要不停回溯反复试，还得担心花园四种花被占满。但这道题多给了一个限制。
每个花园顶多 3 个邻居，花却有 4 种
要看透一点：每个花园最多 3 条小路，即最多 3 个相邻花园。轮到它选花时，这 3 个邻居撑死只占 3 种花色，可我们有 4 种，第 4 种永远留得出来。
有了这保证，做法朴素到底：按编号逐个花园，看它已种花的邻居用了哪些花色，从 1 到 4 挑第一个没被占的种下，选完就定、绝不回头。这就是贪心染色——每步拿当下能用的最小花色，4 种花对付 3 个邻居怎么都够。
从建图到逐个挑色，一趟怎么走完
先建邻接表，即每个花园记一张自己连到谁的表。遍历 paths 的每个 [x, y]，编号从 1 起、下标从 0 起要各减 1，再让两者互相记进对方的邻居列表——小路双向，两边都记。
然后按下标 0 到 n-1 逐个花园 x：把邻居已种的花色收成集合 used，让 c 从 1 数到 4，碰到第一个不在 used 里的写进 ans[x] 后跳出。每个花园只看一次邻居、挑一次色，没有回退。
拿三个围成三角的花园走一遍
就用题面的 n=3、paths=[[1,2],[2,3],[3,1]]。三条边各减 1 后是 0-1、1-2、2-0，每个花园都连着另外两个。
花园 1（下标 0）：邻居 2、3 都没种，used 为空，种花色 1。花园 2（下标 1）：邻居 1 已是花色 1、邻居 3 还空，used={1}，跳过 1、种花色 2。花园 3（下标 2）：邻居 1 是花色 1、邻居 2 是花色 2，used={1,2}，种花色 3。
得到 ans=[1,2,3]。沿三条边验一遍：花园 1 的花色 1 和 2 的花色 2 不同、2 与 3 不同、3 与 1 不同，全合法。三角里两两相邻，被迫用满三色，贪心正好给出。
线性复杂度，再看两个极端
建图遍历每条小路是 O(m)，主循环每个花园看一次全部邻居、总数是边数两倍，合计时间 O(n+m)；邻接表占 O(n+m) 空间，标记花色只 5 个位置是常数。n 是花园数、m 是小路条数。
两个极端也稳：没有小路时人人种花色 1；三花园成三角被逼用满三色，贪心照样给对。真正容易写错的在别处——双向小路只记单边，某些相邻关系看不见、可能给相邻花园种同色；编号忘减 1 直接当下标，越界或种错花园；还有人怕 4 种花不够非加兜底，度不超过 3 早锁死空位，多此一举。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条主线:建图,按编号逐个花园,挑第一个邻居没用过的花色。最多 3 个邻居占不满 4 种花,所以一定挑得到。
总览 · 5 个花园和它们的小路：先把这张图看明白。五个圆圈是五个花园,编号 1 到 5,圈和圈之间的连线是小路,小路两头的花园算相邻。题目要我们给每个花园种一种花,花一共 4 种,用 1 到 4 表示,要求是:有小路直接相连的两个花园,花色必须不一样。提前把答案说出来,最后这五个花园会依次种上花色 1、2、3、1、3,下面一步一步把它选出来。
关键 · 每个花园最多 3 条小路：动手之前先想清楚一件事,这件事决定了为什么可以放心地贪心。题目保证每个花园最多只有 3 条小路,也就是最多 3 个相邻花园。轮到给某个花园选花时,这最多 3 个邻居,撑死了也只能占用 3 种花色。可我们手里有 4 种花。3 比 4 小,所以不管邻居怎么占,4 种花色里永远至少剩一种是空的。既然总有得选,我们就按花园编号一个个来,每个花园挑一种邻居没用过的花就行,绝不会卡住。
轮到 1 号花园：从 1 号花园开始。先看看它的邻居有没有已经种花的,有的话那些花色就不能用了。1 号的邻居是 2 号和 3 号。
看邻居 2 号：先看邻居 2 号。2 号现在还没轮到,是空地,不会限制 1 号的选择,跳过。
看邻居 3 号：再看邻居 3 号。3 号也还没种花,同样不影响。1 号的两个邻居都看完了,都是空的。
1 号种花色 1：它的两个邻居都还没种花,没有任何花色被占用。那就直接从最小的花色 1 开始挑,花色 1 空着,1 号花园就种花色 1。这是种下的第一朵花。
轮到 2 号花园：轮到 2 号花园。它的小路最多,邻居有三个:1 号、3 号和 5 号,正好卡在最多 3 条的上限。挨个看它们种了什么。
看邻居 1 号：先看邻居 1 号。1 号刚才种的是花色 1,所以花色 1 这会儿对 2 号来说不能用了,把它记下来。
看邻居 3 号：再看邻居 3 号。3 号还没种花,是空地,先跳过。
看邻居 5 号：最后看邻居 5 号。5 号也还没种,同样跳过。三个邻居看完,被占用的只有花色 1。
2 号种花色 2：统计下来,只有花色 1 被邻居占用了。现在从花色 1 往上找第一个没被占的:花色 1 被 1 号占了不能用,花色 2 还空着,2 号花园就种花色 2。
轮到 3 号花园：轮到 3 号花园。它也有三个邻居:1 号、2 号和 4 号。继续一个个看它们用了哪些花色。
看邻居 1 号：先看邻居 1 号,它种的是花色 1,把花色 1 记成被占用。
看邻居 2 号：再看邻居 2 号,它种的是花色 2,花色 2 也被占用了。现在 3 号身边已经有两种花色不能用。
看邻居 4 号：最后看邻居 4 号,它还没种花,跳过。这一轮被占用的是花色 1 和花色 2。
3 号种花色 3：邻居一共占用了花色 1 和花色 2。从 1 往上找:花色 1 被占,花色 2 也被占,花色 3 终于空着,3 号花园就种花色 3。你看,贪心会自动跳过被占的花色,挑到第一个能用的。
轮到 4 号花园：轮到 4 号花园,邻居是 3 号和 5 号。看它们的花色。
看邻居 3 号：先看邻居 3 号,它刚种的是花色 3,把花色 3 记成被占用。
看邻居 5 号：再看邻居 5 号,它还没种花,跳过。这一轮只有花色 3 被占。
4 号种花色 1：只有花色 3 被占用。从花色 1 开始找,花色 1 空着就能用,4 号花园种花色 1。这里有个重点:4 号和 1 号都种了花色 1,但它们之间没有小路相连,不相邻的花园花色完全可以重复,这正是只用 4 种花就够的原因。
轮到 5 号花园：最后轮到 5 号花园,它的邻居是 4 号和 2 号。看完这两个就大功告成了。
看邻居 4 号：先看邻居 4 号,它种的是花色 1,记下花色 1 被占。
看邻居 2 号：再看邻居 2 号,它种的是花色 2,花色 2 也被占。5 号身边有两种花色不能用。
5 号种花色 3：邻居占用了花色 1 和花色 2。从 1 往上找,花色 1 被占,花色 2 被占,花色 3 空着,5 号花园种花色 3。五个花园全部种好。
完成 · 对照答案：五个花园全部种好,花色依次是 1、2、3、1、3。回头沿着每条小路验一遍:1 号花色 1 和 2 号花色 2 不同,1 号和 3 号花色 3 不同,2 号和 3 号不同,3 号和 4 号花色 1 不同,4 号和 5 号花色 3 不同,2 号和 5 号也不同,全部小路两头都不一样,符合要求。整道题就一句话:因为每个花园最多 3 个邻居、却有 4 种花,所以按编号一个个贪心地避开邻居用过的花色,一定能种满,永远不会卡住。
边界想清:没有小路时人人种花色 1;三个花园围成三角时被迫用三种花色,贪心都能正确给出。
面试重点:4 种花比最大度数 3 多一,这个余量让贪心免回溯;若花色减到 3 就可能卡住,退回到一般图着色。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]: g = defaultdict(list) for x, y in paths: x, y = x - 1, y - 1 g[x].append(y) g[y].append(x) ans = [0] * n for x in range(n): used = {ans[y] for y in g[x]} for c in range(1, 5): if c not in used: ans[x] = c break return ans复杂度
- 时间：O(n + m)，n 是花园数,m 是小路条数。建邻接表遍历所有小路是 O(m);主循环对每个花园看它的全部邻居,所有花园的邻居总数等于边数的两倍,加上每园固定挑 4 种花色,合起来是 O(n + m)
- 空间：O(n + m)，邻接表存下全部边,占 O(n + m);答案数组 O(n);标记花色用的布尔数组只有 5 个位置,是常数,可忽略
易错点
面试追问把动画讲成自己的话
追问这道题为什么不需要回溯或者更复杂的图着色算法?
追问如果把花的种类从 4 改成 3,这套贪心还成立吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按字典序排列最小的等效字符串
LeetCode 1061 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题