1042. 不邻接植花
有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。
另外，所有花园 最多 有 3 条路径可以进入或离开.
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
示例 1：
输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]
题解
/**
* @param {number} n 花园的数量
* @param {number[][]} paths 花园之间的路径列表
* @return {number[]} 返回一个长度为 n 的数组，代表每个花园所涂的颜色
*/
var gardenNoAdj = function(n, paths) {
// 构造邻接表，用 nei[i] 存储与第 i 个花园相邻的花园编号
let nei = new Array(n).fill(null).map(() => []);
for (let path of paths) {
nei[path[0] - 1].push(path[1] - 1);
nei[path[1] - 1].push(path[0] - 1);
}
// 初始化结果数组 res，用 res[i] 存储第 i 个花园所涂的颜色
let res = new Array(n).fill(0);
// 遍历每个花园，对其进行着色
for (let i = 0; i < n; ++i) {
let usedColor = new Array(5).fill(false); // 初始化 usedColor，用于记录相邻花园已经使用的颜色
// 遍历第 i 个花园的相邻花园，统计已经使用的颜色
for (let vertex of nei[i]) {
usedColor[res[vertex]] = true;
}
// 找到第一个未使用的颜色
for (let j = 1; j <= 4; ++j) {
if (!usedColor[j]) {
res[i] = j;
break;
}
}
}
return res;
};
复杂度分析
时间复杂度：O(n+m)，其中 n 表示花园的数目，m 表示 paths 的数目。由于题目中每个花园的邻接节点数目不超过 3 个，因此每个节点的边不超过 3 条，所以遍历所有的节点与所有的边需要的总的时间不超过 O(m+n)。
空间复杂度：O(n+m)，其中 n 表示花园的数目，m 表示 paths 的数目。需要存储每个节点的邻接节点，总共需要的空间为 O(n+m)。
