You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.
All gardens have at most 3 paths coming into or leaving it.
Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.
Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.
你有 n 個花園，編號從 1 到 n，以及一個路徑陣列 paths， 其中 paths[i] = [xi, yi] 表示花園 xi 到 花園 yi 之間的雙向路徑。 在每個花園中，你想種植 4 種花卉中的一種。 每個花園最多有 3 條路徑進出。 你的任務是為每個花園選擇一種花卉，只得任兩個由路徑連接的花園種植的花卉種類不同。 回傳一個滿足此條件的答案陣列 answer，其中 answer[i] 表示第 i + 1 個花園中種植的花卉種類。 花卉種類已 1, 2, 3, 4 表示，並保證答案存在。
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]
Solution:
這題需要一點圖像的想像力，比如：
題目說這是雙向路徑，也就是比次相連，如果 花園 1 連到花園 2，那花園 2 一定也連到花園 1。
花園 1 <--> 花園 2
\ /
\ /
花園 3
paths = [[1,2],[2,3],[3,1]]
edge = [[1, 2], [0, 2], [1, 0]]
edge[0] = [1, 2] // 花園 1 (index 0) 和 index 1, index 2 的花園有路相連。
edge[1] = [0, 2] // 花園 2 (index 1) 和 index 0, index 2 的花園有路相連。
edge[2] = [1, 0] // 花園 3 (index 2) 和 index 1, index 0 的花園有路相連。
有了 edge 這個陣列可以幫助我們快速查找花園的鄰居，
而每個花園最多只有 3 個鄰居，而花種有 4 中，所以一定可以找到一個合法的話，
我們從 1 ~ 4 選一個沒被鄰居使用的花付給該花園。
Code 1: BigO(n x m)
function gardenNoAdj(n: number, paths: number[][]): number[] {
const edge: number[][] = Array.from({length: n}, () => []);
for (const [x, y] of paths) {
edge[x - 1].push(y - 1);
edge[y - 1].push(x - 1);
}
const ans: number[] = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
const used: Set = new Set();
for (const nei of edge[i]) {
if (ans[nei] !== 0) used.add(ans[nei]);
}
for (let flower = 1; flower <= 4; flower++) {
if (!used.has(flower)) {
ans[i] = flower;
break;
}
}
}
return ans;
};
FlowChart:
Example 1
Input: n = 3, paths = [[1,2],[2,3],[3,1]] edge [ [ 1, 2 ], [ 0, 2 ], [ 1, 0 ] ] ans [ 0, 0, 0 ] ans [ 1, 0, 0 ] ans [ 1, 2, 0 ] return ans; // [ 1, 2, 3 ]
Example 2
Input: n = 4, paths = [[1,2],[3,4]] edge [ [ 1 ], [ 0 ], [ 3 ], [ 2 ] ] ans [ 0, 0, 0, 0 ] ans [ 1, 0, 0, 0 ] ans [ 1, 2, 0, 0 ] ans [ 1, 2, 1, 0 ] return ans; // [ 1, 2, 1, 2 ]
Example 3
Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] edge [ [ 1, 3, 2 ], [ 0, 2, 3 ], [ 1, 3, 0 ], [ 2, 0, 1 ] ] ans [ 0, 0, 0, 0 ] ans [ 1, 0, 0, 0 ] ans [ 1, 2, 0, 0 ] ans [ 1, 2, 3, 0 ] return ans; // [ 1, 2, 3, 4 ]