1042-不邻接植花

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

有 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]

示例 2：

**输入：** n = 4, paths = [[1,2],[3,4]]
**输出：** [1,2,1,2]

示例 3：

**输入：** n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
**输出：** [1,2,3,4]

提示：

  • 1 <= n <= 104
  • 0 <= paths.length <= 2 * 104
  • paths[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • 每个花园 最多 有 3 条路径可以进入或离开

方法一：颜色标记

思路与算法

由于每个花园最多有 3 条路径可以进入或离开，这就说明每个花园最多有 3 个花园与之相邻，而每个花园可选的种植种类有 4 种，这就保证一定存在合法的种植方案满足题目要求。花园中种植不同的花可以视为每个花园只能标记为给定的4种颜色为 1,2,3,4 中的一种，初始化时我们可以为每个花园标记为颜色 0。对于第 i 个花园，统计其周围的花园已经被标记的颜色，然后从未标记的颜色中选一种颜色给其标记即可。整体标记过程如下：

  • 首先建立整个图的邻接列表 adj ；
  • 初始化时，将每个花园节点的颜色全部标记为 0；
  • 遍历每个花园，并统计其相邻的花园的颜色标记，并从未被标记的颜色中找到一种颜色给当前的花园进行标记；
  • 返回所有花园的颜色标记方案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> adj(n);
        for (auto &path : paths) {
            adj[path[0] - 1].emplace_back(path[1] - 1);
            adj[path[1] - 1].emplace_back(path[0] - 1);
        }
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            vector<bool> colored(5, false);
            for (auto &vertex : adj[i]) { 
                colored[ans[vertex]] = true;
            }
            for (int j = 1; j <= 4; j++) { 
                if (colored[j] == 0) { 
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
};
[sol1-Java]
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
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] path : paths) {
            adj[path[0] - 1].add(path[1] - 1);
            adj[path[1] - 1].add(path[0] - 1);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            boolean[] colored = new boolean[5];
            for (int vertex : adj[i]) { 
                colored[ans[vertex]] = true;
            }
            for (int j = 1; j <= 4; j++) { 
                if (!colored[j]) { 
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        adj = [[] for i in range(n)]
        for path in paths:
            adj[path[0] - 1].append(path[1] - 1)
            adj[path[1] - 1].append(path[0] - 1)
        ans = [0] * n
        for i in range(n):
            colored = [False] * 5
            for vertex in adj[i]:
                colored[ans[vertex]] = True
            for j in range(1, 5):
                if not colored[j]:
                    ans[i] = j
                    break
        return ans
[sol1-C#]
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
public class Solution {
    public int[] GardenNoAdj(int n, int[][] paths) {
        IList<int>[] adj = new IList<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        foreach (int[] path in paths) {
            adj[path[0] - 1].Add(path[1] - 1);
            adj[path[1] - 1].Add(path[0] - 1);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            bool[] colored = new bool[5];
            foreach (int vertex in adj[i]) { 
                colored[ans[vertex]] = true;
            }
            for (int j = 1; j <= 4; j++) { 
                if (!colored[j]) { 
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
}
[sol1-C]
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
int* gardenNoAdj(int n, int** paths, int pathsSize, int* pathsColSize, int* returnSize) {
    int adj[n][3], adjSize[n];
    memset(adjSize, 0, sizeof(adjSize));
    for (int i = 0; i < pathsSize; i++) {
        int x = paths[i][0] - 1;
        int y = paths[i][1] - 1;
        adj[x][adjSize[x]++] = y;
        adj[y][adjSize[y]++] = x;
    }
    int *ans = (int *)calloc(sizeof(int), n);
    for (int i = 0; i < n; i++) {
        bool colored[5];
        memset(colored, 0, sizeof(colored));
        for (int j = 0; j < adjSize[i]; j++) { 
            int vertex = adj[i][j];
            colored[ans[vertex]] = true;
        }
        for (int j = 1; j <= 4; j++) { 
            if (colored[j] == 0) { 
                ans[i] = j;
                break;
            }
        }
    }
    *returnSize = n;
    return ans;
}
[sol1-Go]
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
func gardenNoAdj(n int, paths [][]int) []int {
    adj := make([][]int, n)
    for i := 0; i < n; i++ {
        adj[i] = []int{}
    }
    for _, path := range paths {
        adj[path[0]-1] = append(adj[path[0]-1], path[1]-1)
        adj[path[1]-1] = append(adj[path[1]-1], path[0]-1)
    }
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        colored := make([]bool, 5)
        for _, vertex := range adj[i] {
            colored[ans[vertex]] = true
        }
        for j := 1; j <= 4; j++ {
            if !colored[j] {
                ans[i] = j
                break
            }
        }
    }
    return ans
}

[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var gardenNoAdj = function(n, paths) {
    let adj = new Array(n).fill(null).map(() => []);
    for (let path of paths) {
        adj[path[0] - 1].push(path[1] - 1);
        adj[path[1] - 1].push(path[0] - 1);
    }
    let ans = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        let colored = new Array(5).fill(false);
        for (let vertex of adj[i]) {
            colored[ans[vertex]] = true;
        }
        for (let j = 1; j <= 4; j++) {
            if (!colored[j]) {
                ans[i] = j;
                break;
            }
        }
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n + m)，其中 n 表示花园的数目，m 表示 paths 的数目。由于题目中每个花园的邻接节点数目不超过 3 个，因此每个节点的边不超过 3 条，所以遍历所有的节点与所有的边需要的总的时间不超过 O(m + n)。

  • 空间复杂度：O(n + m)，其中 n 表示花园的数目，m 表示 paths 的数目。需要存储每个节点的邻接节点，总共需要的空间为 O(n + m)。

 Comments
On this page
1042-不邻接植花