#1042
Flower Planting With No Adjacent
specialist · 860 · lc medium +31 · verified · 53.4% accepted · 1,569 likes · top 44%
Description
You have n gardens labeled 1 to n connected by paths, where paths[i] = [xi, yi] is a bidirectional path. Each garden must receive exactly one of 4 flower types, and no two directly connected gardens may share a type.
Every garden has at most 3 paths.
Return any valid flower assignment as an array answer where answer[i] is the flower type (1–4) for garden i+1.
Example 1:
Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].
Example 2:
Input: n = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]
Example 3:
Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]
Code
1
2
3