1042. Flower Planting With No Adjacent

题目信息

题号:

1042

难度:

Medium

主题:

无向图、四种颜色、相邻约束

原题:

LeetCode 1042

重点:

花园编号从 1 开始,每个花园度数至多为 3;需从四种花中任选一种,使每条路径两端花色不同,任意合法答案均可

题目重述

有 n 个花园,编号为 1 到 n。数组 paths 中每个 [x, y] 表示花园 x 与花园 y 之间有一条双向路径。每个花园最多连接三个其他花园。

需要给每个花园种植编号 1 到 4 中的一种花,使任意由路径直接相连的两个花园花种不同。返回长度为 n 的数组,其中第 i 项是花园 i + 1 的花种编号;若有多种方案,可返回任意一种。

1 <= n <= 10^4,0 <= paths.length <= 2 * 10^4,不存在自环或重复路径,且每个花园的路径数不超过 3。

自建示例

环形连接可以交替使用两种花:

输入:n = 4, paths = [[1,2],[2,3],[3,4],[4,1]]
输出:[1,2,1,2]
解释:每条路径的两个端点都使用不同花种;其他满足约束的花种分配也同样合法。

只有一个孤立花园:

输入:n = 1, paths = []
输出:[1]
解释:没有相邻花园限制,四种花中的任意一种都可使用。