1042. Flower Planting With No Adjacent¶
题目信息¶
- 题号:
1042
- 难度:
Medium
- 主题:
无向图、四种颜色、相邻约束
- 原题:
- 重点:
花园编号从
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]
解释:没有相邻花园限制,四种花中的任意一种都可使用。