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``。 自建示例 -------- 环形连接可以交替使用两种花: .. code-block:: text 输入:n = 4, paths = [[1,2],[2,3],[3,4],[4,1]] 输出:[1,2,1,2] 解释:每条路径的两个端点都使用不同花种;其他满足约束的花种分配也同样合法。 只有一个孤立花园: .. code-block:: text 输入:n = 1, paths = [] 输出:[1] 解释:没有相邻花园限制,四种花中的任意一种都可使用。