题目简介：
有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。
另外，所有花园 最多 有 3 条路径可以进入或离开.
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
示例 1：
1
2
3
4
5
6
7
| 输入：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]
|
提示：
1 <= n <= 10^40 <= paths.length <= 2 * 10^4paths[i].length == 21 <= xi, yi <= nxi != yi- 每个花园 最多 有 3 条路径可以进入或离开
思路：
首先定义邻接表，将每个花园能联通的花园都储存起来。
初始化时，将每个花园节点的颜色全部标记为 0；
遍历每个花园，并统计其相邻的花园的颜色标记，并从未被标记的颜色中找到一种颜色给当前的花园进行标记；
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<vector<int>> graph(n + 1);
for(int i = 0; i < paths.size(); i++){
graph[paths[i][0]].push_back(paths[i][1]);
graph[paths[i][1]].push_back(paths[i][0]);
}
vector<int> res(n);
for(int i = 0; i < n; i++){
vector<int> color(5);
for(auto j : graph[i + 1]){
color[res[j - 1]] = 1;
}
for(int j = 1; j <= 4; j++){
if(color[j] == 0){
res[i] = j;
break;
}
}
}
return res;
}
};
|
